Saved Bookmarks
| 1. |
What is the smallest value of n such that an algorithm whose running time is 50n3 runs faster than an algorithm whose running time is 3n on the same machine? |
||||||||||||||||||
|
Answer» The running time of an algorithm depends upon various characteristics and slight variation in the characteristics varies the running time. The algorithm efficiency and performance in comparison to alternate algorithm is best described by the order of growth of the running time of an algorithm. Suppose one algorithm for a problem has time complexity as c3n2 and another algorithm has c1n3 +c2n2 then it can be easily observed that the algorithm with complexity c3n2 will be faster than the one with complexity c1n3 +c2n2 for sufficiently larger values of n. Whatever be the value of c1, c2 and c3 there will be an ‘n’ beyond which the algorithm with complexity c3n2 is faster than algorithm with complexity c1n 3 +c2n 2 , we refer this n as breakeven point. Here running time of algorithms are 50*n3 and 3n ,if we compare both as shown in the following table, we find that 10 is the smallest value of n (9.8) for which 50*n3 will run faster than 3n .
|
|||||||||||||||||||