Another method that can often be used to find Big O is to look at the ratio of times as the size of input is doubled. Ratios that are approximately powers of 2 are easily recognized:
|Ratio||Power of 2||Big O|
|2+||21+||n * log(n) ?|
Since the ratio is about 4, this function is O(n2).
Contents Page-10 Prev Next Page+10 Index