## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

So, 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.

Comment hidden because of low score. Click to expand.
0

WRONG.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

RIGHT.

O(n) is an upper bound. So saying that an algorithm is O(n) in the worst case is that it is linear or better at all time. That is all. It could be constant, log n, etc.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.