# complexity

Discussion in 'C Programming' started by raghu, Dec 10, 2006.

1. ### raghuGuest

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

Thanks a lot.

raghu, Dec 10, 2006

2. ### coldsunGuest

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.

coldsun, Dec 10, 2006

3. ### Keith ThompsonGuest

"raghu" <> writes:
> 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) <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.

Keith Thompson, Dec 10, 2006
4. ### SourcererGuest

"Keith Thompson" <> wrote in message
news:...
> "raghu" <> writes:
>> 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/

Sourcerer, Dec 10, 2006
5. ### Guest

On Dec 10, 1:19 pm, "raghu" <> wrote:
> 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, 2006