Share this:
Google+
< Contents  Previous  Next >
By this point, you have already a rough idea of what bigoh notation is about. In this section, we will refine that idea by connecting the asymptotic functions and estimate running time. Which bigoh notation has the fastest running time? Is factorial asymptotic function O(n!) faster than polynomial such as O(n^3)?
Let us compare several common asymptotic functions and estimate running time. Table below shows the estimated running time if one step takes about a microsecond (=1/1,000,000 second). The asymptotic functions have been sorted from the fastest to the slowest. This table make clear to us that depending on the problem size at hand, any algorithm that slower than O(n^2) is too slow to be used for big data size. Some algorithm may take more than a millennium (1000 years) if we run it. Algorithm with factorial running time cannot be used even for the problem size of 25 data points. Some algorithm with polynomial running time of O(n^3) cannot be used for large problem higher than 10,000 data points. The empty cells in the table means too large to be computed.
function 
Problem size, n 

1 
10 
25 
50 
100 
500 
1,000 
10,000 
100,000 
1,000,000 

1 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
log(log(n)) 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
log(n) 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
Sqrt(n) 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
n 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
1 s 
n log(n) 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
6 s 
n^2 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
1 s 
1.67 s 
2.78 hours 
1.65 weeks 
n^3 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
1 s 
2.1 s 
16.7 min 
1.65 weeks 
3.17 decades 
31.7 Millennium 
n^log(n) 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
< 1 s 
19.2 s 
16.7 min 
317 years 
3.17 x 10^8 Millennium 
3.17 x10^19 Millennium 
2^n 
< 1 s 
< 1 s 
33.5 s 
35 years 
4 x 10^13 Millennium 
10^134 Millennium 
3.4 x 10^284 Millennium 



3^n 
< 1 s 
< 1 s 
9.8 days 
2.3 x 10^7 Millennium 
1.6 x 10^31 Millennium 
10^222 Millennium 




n! 
< 1 s 
3.6 s 
4.9 x 10^8 Millennium 
9.6 x 10^47 Millennium 
2.9 x 10^141 Millennium 





Clearly, the list of asymptotic functions above are not exhaustive. You can compute the estimate computational time of an asymptotic function by yourself using spreadsheet such as Excel. If one step computational time is (in the table above, we set seconds), and the asymptotic function is then the formula to compute the computational time is simply
The number of seconds in time as shown in the table below is useful to convert the seconds into more readable time:
Time 
Number of Seconds 
A Second 
1 
A Minute 
60 
An Hour 
3,600 
A Day 
86,400 
A Week 
604,800 
A Month 
2,592,000 
A Quarter 
7,776,000 
A Semester 
15,552,000 
A Year 
31,536,000 
A Decade 
315,360,000 
A Century 
3,153,600,000 
A Millennium 
31,536,000,000 
The drastic change in running time due to the nonlinear nature of the algorithm is sometimes difficult to perceive by many programmers. People tend to think in linear fashion. Let us take an example. Floyd–Warshall algorithm is wellknown to have running time complexity of O(n^3) where n is the number of nodes in a network. Suppose for a moment, you either do not know anything about the algorithm complexity or you simply ignore to compute it. When you run the Floyd–Warshall algorithm for 100 nodes, the algorithm can run in just about 1 second. You were happy. Next, when you run the same algorithm for 500 nodes, the algorithm can run in just about 2 seconds. You increased the input size by 5 times but the running time is just about double. This little experience will make you think in linear fashion. You thought that if you double the number of nodes, the running time is probably just about 4 seconds. It does not happen that way. If the number of nodes is doubled, the running time becomes 17 minutes. At this point, you can probably still bear it. Now, since you are such ignorance to the complexity of algorithm, if the number of nodes in the network is multiplied by 10, the same Floyd–Warshall algorithm will run for more than a week on the same computer. A city network typically has more than 100,000 nodes and running this O(n^3) algorithm is clearly impractical in that same computer because it will take more than 3 decades to finish it.
The nice lesson is if you do not compute the time complexity of the algorithm and rely on the computer run time to monitor it, you will end up wasting your time waiting for the computer to run. In fact, some algorithm may never finish to run it in your whole life time.
In the next section, let us identify some best algorithms based on the order of time complexity.
< Contents  Previous  Next >
These tutorial is copyrighted .
How to cite this tutorial:
Teknomo, Kardi. (2017) Analysis of Algorithm .
http://people.revoledu.com/kardi/tutorial/Algorithm/