| | |
Time complexity of algorithm
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
![]() |
>How to calculate time complexity of any algorithm or program ....
The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:
Is constant. The running time of the statement will not change in relation to N.
Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.
Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.
Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.
Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.
In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( <type> ) where <type> is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).
Note that none of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.
The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:
statement;
for ( i = 0; i < N; i++ ) statement;
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}while ( low <= high ) {
mid = ( low + high ) / 2;
if ( target < list[mid] )
high = mid - 1;
else if ( target > list[mid] )
low = mid + 1;
else break;
}void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( <type> ) where <type> is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).
Note that none of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.
I'm here to prove you wrong.
•
•
Join Date: May 2005
Posts: 1
Reputation:
Solved Threads: 0
Big Oh denotes "fewer than or the same as" <expression> iterations.
Big Omega denotes "more than or the same as" <expression> iterations.
Big Theta denotes "the same as" <expression> iterations.
Little Oh denotes "fewer than" <expression> iterations.
Little Omega denotes "more than" <expression> iterations.
Big Omega denotes "more than or the same as" <expression> iterations.
Big Theta denotes "the same as" <expression> iterations.
Little Oh denotes "fewer than" <expression> iterations.
Little Omega denotes "more than" <expression> iterations.
•
•
Join Date: Aug 2005
Posts: 11
Reputation:
Solved Threads: 0
Thanks for the lovely explanation Narue. I have a couple of questions though.
I assume that when you said the complexity for the following code was O(N log (N)), you meant the average case measure?
If I had to calculate the best and worst, how would I do that?
I tried to do best, and correct me if I'm wrong but that would be when the list has 1 element, so the best case scenario would be O(1)?
I assume that when you said the complexity for the following code was O(N log (N)), you meant the average case measure?
void quicksort ( int list[], int left, int right )
{
int pivot = partition ( list, left, right );
quicksort ( list, left, pivot - 1 );
quicksort ( list, pivot + 1, right );
}If I had to calculate the best and worst, how would I do that?
I tried to do best, and correct me if I'm wrong but that would be when the list has 1 element, so the best case scenario would be O(1)?
>I assume that when you said the complexity for the following code was
>O(N log (N)), you meant the average case measure?
Correct. Average and best case complexities are easier to figure out than worst case.
>If I had to calculate the best and worst, how would I do that?
To calculate the best case, simply assume a perfect partition right down the middle each time. This will roughly halve the data set and the time complexity is O(Nlog N), just like the average case, except it's a tighter bound, so while Big O is correct, you can use Big Theta to be more correct.
To calculate the worst case, assume the worst possible partition, which would basically be the left or rightmost item, so one half contains a single element and the other half contains everything else. It's fairly easy to see that this is linear, so the worst case time complexity is O(N).
>I tried to do best, and correct me if I'm wrong but that would be when
>the list has 1 element, so the best case scenario would be O(1)?
You could say that, but Big O notation doesn't assume the number of elements. It's a measurement of growth as the data set gets larger. So O(1) means that if you double the number of elements, the time the algorithm takes is the same. O(N) means that if the number of elements doubles, so does the time the algorithm takes to process them.
>O(N log (N)), you meant the average case measure?
Correct. Average and best case complexities are easier to figure out than worst case.
>If I had to calculate the best and worst, how would I do that?
To calculate the best case, simply assume a perfect partition right down the middle each time. This will roughly halve the data set and the time complexity is O(Nlog N), just like the average case, except it's a tighter bound, so while Big O is correct, you can use Big Theta to be more correct.
To calculate the worst case, assume the worst possible partition, which would basically be the left or rightmost item, so one half contains a single element and the other half contains everything else. It's fairly easy to see that this is linear, so the worst case time complexity is O(N).
>I tried to do best, and correct me if I'm wrong but that would be when
>the list has 1 element, so the best case scenario would be O(1)?
You could say that, but Big O notation doesn't assume the number of elements. It's a measurement of growth as the data set gets larger. So O(1) means that if you double the number of elements, the time the algorithm takes is the same. O(N) means that if the number of elements doubles, so does the time the algorithm takes to process them.
I'm here to prove you wrong.
•
•
Join Date: Aug 2005
Posts: 11
Reputation:
Solved Threads: 0
Thanks for that narue.
One more question. I have understood how to calculate the O of a simple algorithm but does that O depend upon the size of N as well? I read in an online book somewhere that O will have two values for the same algorithm, one when N was very large and another when N is small. Is that correct? If so, how do I calculate the value of say,
"3 n^2 - 100 n + 6" for a very small n?
I know the complexity for the above will be O(n^2) for very large n but what about very small n?
One more question. I have understood how to calculate the O of a simple algorithm but does that O depend upon the size of N as well? I read in an online book somewhere that O will have two values for the same algorithm, one when N was very large and another when N is small. Is that correct? If so, how do I calculate the value of say,
"3 n^2 - 100 n + 6" for a very small n?
I know the complexity for the above will be O(n^2) for very large n but what about very small n?
O notation removes all constants so that you're left with the largest growth rate, which will be dominant as N increases. Naturally, when N is small, the constants will be the dominant factor, so it can make sense to keep them in the equation rather than removing them if N is guaranteed to be small.
>I know the complexity for the above will be O(n^2) for very large n but what about very small n?
It will still be O(n^2), but if n is 5, for example, 100n totally dominates the algorithm as opposed to if n is 5000, where n^2 dominates.
>I know the complexity for the above will be O(n^2) for very large n but what about very small n?
It will still be O(n^2), but if n is 5, for example, 100n totally dominates the algorithm as opposed to if n is 5000, where n^2 dominates.
I'm here to prove you wrong.
•
•
Join Date: Aug 2005
Posts: 11
Reputation:
Solved Threads: 0
That's what I thought but this page says different, rather the figures on the page say different. It's got me confused.
![]() |
Similar Threads
- calculate time complexity of the algorithm (Computer Science)
- time complexity of algorithm (Computer Science)
- Calculating time complexity (Computer Science)
- Help On Time Complexity Algorithm (Computer Science)
Other Threads in the Computer Science Forum
- Previous Thread: Breakthrough heralds new era of cognitive computing
- Next Thread: Is prostitution more enjoyable than programming?
| Thread Tools | Search this Thread |







