What is the complexity of this algorithm?

Question

procedure max (a[1..n]: integers)
    max := a[1]
    for i := 2 to n
        if max < a[i] then max := a[i]

Is the complexity O(1) or O(n) with the best case scenario? The sequence contains n elements. It is pseudocode.

Answer 1

O(n) - you have to scan n elements, or a factor of n (n/2, n/4 etc) - still O(n).

Answer 2

There's no difference between the best case and worst case asymptotic running times for this algorithm. In all cases, you have to traverse the whole array (n elements) and your algorithm would be O(n).

Theoretically, there's no way you can find the maximum element of an arbitrary array in less than O(n) since you should always visit each element at least once.

Answer 3

The algorithm is O(n) in the best case, average case, and worst case. It also doesn't work, since it only refers to a1 and uses < where it should use >.

Answer 4

If you have code that reads:

for i := 2 to n

Then that code will be O(n) best case.

I'm curious why you think it might be constant time?

Answer 5

Roughly, O(1) means that whatever the size of the input, you can implement the solution in fixed number of steps.

O(n) means that if you have n inputs, the solution will be implemented in An steps (where A is a number, not another variable). Clearly, if you have for loop which counts from 2 to n, that is n cycles, meaning that if you have An input elements, your loop will count from 2 to An, meaning that it is on the same level az the input, so it's O(n). But that's how linear scanning is. :)

Answer 6

You have to traverse the whole array. So the complexity would be O(n).

Answer 7

O(n)

you can achieve the O(1) if the array was sorted, so you'll just return the last element.

but in random arranged elements the best order for this problem is O(n)