473,320 Members | 2,112 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

complexity

How to find the complexity of a C program? Can anyone explain it with
an example...

Thanks a lot.

Dec 10 '06 #1
4 2743
There is, basically, no automatic way to find the complexity of a C
program, or program in any other language. In order to find out the
complexity of an algorithm, you have to perform manual analysis.
"introdcution to algorithms" and the famous TAOCP by Knuth may help you
here.
"raghu дµÀ£º
"
How to find the complexity of a C program? Can anyone explain it with
an example...

Thanks a lot.
Dec 10 '06 #2
"raghu" <ra*********@gmail.comwrites:
How to find the complexity of a C program? Can anyone explain it with
an example...
What exactly do you mean by "complexity"? The language provides no
definition for the term.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Dec 10 '06 #3
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"raghu" <ra*********@gmail.comwrites:
>How to find the complexity of a C program? Can anyone explain it with
an example...

What exactly do you mean by "complexity"? The language provides no
definition for the term.
I believe he means spatial and temporal complexity.

You can find out what the temporal complexity of the program is if you manage to
determine how its time of execution grows with the number of elements it needs
to process. If the execution of the program is independent of the number of
those elements, its temporal complexity is O(1). If it grows in linear
proportion to the number of elements, it is O(n), etc.

For example, if you have defined a node of the binary tree like this

struct node {
int a;
struct node *less;
struct node *more;
};

where less points to a node which contains int a which is smaller than in this
node, and more points to a node where int a is larger than here, then you can
place elements into this tree by using these constraints.

Let's assume you've also balanced the tree. To find a particular element in this
tree, the temporal complexity would be O(ld(n)) (dual logarythm, or logarythm of
base 2).

Spatial complexity is similar, only you look at this not in terms of the time
the program needs to execute, but how much space it requires (usually stack is
observed). If the stack is not dependent on the number of elements you need to
process, the complexity is O(1). If it grows in proportion to the number of
elements, the complexity is O(n), etc.

--
"It is easy in the world to live after the world's oppinion; it easy in solitude
to live after our own; but the great man is he who in the midst of the crowd
keeps with perfect sweetness the independence of solitude."
Ralph Waldo Emerson, Self-reliance 1841
http://pinpoint.wordpress.com/

Dec 10 '06 #4


On Dec 10, 1:19 pm, "raghu" <raghujin...@gmail.comwrote:
How to find the complexity of a C program? Can anyone explain it with
an example...

Thanks a lot.
Well, the complexity i know is the number of distinct paths that can
be executed in a particular function, naturally a big complexity is bad
as it would require more number of test cases to test, more time to
understand the flow and logic involved in a particular function, and
this is know as Mccabe's cyclomatic complexity...

Dec 11 '06 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Paul Keating | last post by:
I have a very simple COM server written in Python that is trying to return a two-dimensional array 268 x 20. The values it contains are some small integers, some short (<29 character) Unicode...
2
by: Brett | last post by:
This statement mentions that complexity kills but can it be avoided? "The kind of scalability I'm talking about is styem scale and compliexity. Anyone who has written large scale systems knows...
4
by: Generic Usenet Account | last post by:
Consider two entities A and B such that there is a 1:n association between them. I mean that associated with each instance of A there are up to n instances of B. Currently in our software we are...
1
by: Jerzy Karczmarczuk | last post by:
Anybody knows where I can find a concrete and guaranteed answer to the following extremely basic and simple question? What is the complexity of appending an element at the end of a list?...
5
by: junky_fellow | last post by:
How do we calculate the complexity of an algorithm? Am i right if i say the complexity of an algorithm is the number of comparisons done in that algorithm? thanx in advance .......
8
by: sam_cit | last post by:
Hi, I came to read this particular statement with respect to reducing the complexity of a code, The usage of functional maps matrices instead of switch statements should be considered. I...
26
by: Lionel B | last post by:
Hi, Anyone know if the Standard has anything to say about the time complexity of size() for std::set? I need to access a set's size (/not/ to know if it is empty!) heavily during an algorithm...
5
by: Joris van Lier | last post by:
Given two implementations of an algorithm how do I determine the relative computational complexity of each? Are there tools that can determine the relative performance of two algorithms or...
3
by: youtoo | last post by:
It has been extensively discussed the time complexity (quadratic) of string concatenation (due to string's immutability). But what is: == the time complexity of string indexing? Is it constant?...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.