# how to find complexity of an algorithm using programming

Page 1 of 1

## 2 Replies - 17932 Views - Last Post: 07 January 2009 - 06:22 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=79705&amp;s=c0fad46635f9e0c6e3b85613f88ddc43&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

Reputation: 0
• Posts: 1
• Joined: 07-January 09

# how to find complexity of an algorithm using programming

Posted 07 January 2009 - 05:25 AM

I want to know that how to find the complexity of an algorithm in programming languages.
Is This A Good Question/Topic? 0

## Replies To: how to find complexity of an algorithm using programming

### #2 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: how to find complexity of an algorithm using programming

Posted 07 January 2009 - 05:43 AM

It depends on what algorithm it is and if it's iterative or recursive. It can also depend on the input size (pseudo-polynomials).

### #11 AmitTheInfinity

• C Surfing ∞

Reputation: 119
• Posts: 1,565
• Joined: 25-January 07

## Re: how to find complexity of an algorithm using programming

Posted 07 January 2009 - 06:22 AM

Time Complexity : The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm.

So we denote it in form of o(n) notation. [There are different notations for best , average, worst case (symboled by theta, omega and bit O)]. Generally a time complexity will be the time required for the most time consuming activity of algorithm.

e.g.
```void print()
{
for(int i=0;i<n,i++)
{
printf("%d ",i);
}

for(int j=0;j<n,j++)
{
for(int i=0;i<n,i++)
{
printf("%d  ",i*j);
}
}
}

```

This will have time complexity of O(n^2) and the nested for loop will be the time consuming activity in any case.

In general calculation of time complexity of algorithms can be done using following calculations...

return 0; - statement like this executes in defined time [say 1 unit] so it's time complexity will be constant.

for ( i = 0; i < N; i++ ) printf("a"); - this for loop will take n iterations to finish, so total statement executions will be 3N+1, as this is directly proportional to N the time complexity here will be O(n).

you already have one example of O(n^2) above.

```while ( low <= high ) {
mid = ( low + high ) / 2;

if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}

```

This code uses divide and conquer strategy, which makes it logarithmic i.e. The running time of the algorithm is proportional to the number of times N can be divided by 2. so it's complexity will be O(log n).

There are complexities like O(n^3), O(n*log n) etc. You can explore about them by yourself.

This and this can be a good resource on it.

Space Complexity : The space complexity of a problem is a related concept that measures the amount of space or memory required by the algorithm. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper.

So similar to time complexity, this also considers the highest memory consuming part of the code as the decider of space complexity.
This can be a good resource on it.

This post has been edited by AmitTheInfinity: 07 January 2009 - 06:23 AM