"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/