complexity

[raghu]

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

Thanks a lot.

 

[coldsun]

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 дµÀ£º
"

 

[Keith Thompson]

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.

 

[Sourcerer]

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/

 

[sam_cit]

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...