Interview Question
Country: United States
In general having O (n) time means that the time grows no worse then linearly as n grows, where n is the number of data elements the algorithm operates on.
However when we say an ago runs in O (n) IN THE WORST CASE we usually contrast that with a better O in the average case, such as O (logn). It means that there are some, particularly troublesome combinations of the input data that may cause a linear performance, but in average the algorithm behave better than that.
We mean to say that it would perform some computation task N number of times. In fact it is not strictly correct either, we mean to say that there is some task comparision/swap/etc that gets performed a number of times and this number is proportional to N.
- Pavan Dittakavi October 25, 2014So, if this N increases, then the number of comparisions involved would also increase linearly.
Take linear search for example. Worst case is not finding an element. So, if there are 100 elements, in the worst case, we would end up making 100 comparisions [ a[0],a[1]...a[99] ].
Similarly, if we are looking at an array of size 1000, we would consequently make 1000 comparisons. Note the linear nature here.
Similarly, there are algorithms[ many sorting algorithms ] that perform O(n2) [n square] in the worst case.