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.
-
@Ben, I modified the code to match what I believe was your intent since, as @Artelius pointed out, it won't run as-is (even if pseudo-code).paxdiablo– paxdiablo2009-11-11 07:22:19 +00:00Commented Nov 11, 2009 at 7:22
Add a comment
|
7 Answers
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.
3 Comments
Artelius
There's no way to improve on O(n) using conventional hardware.
Mehrdad Afshari
Artelius: We're usually talking about the Random Access Machine model by default. Of course, the running time can be different when you switch to other computational models.
Artelius
@Mehrdad: I know, I was being cheeky. A bit annoyed that I haven't been upvoted despite describing some bugs in the code.
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 >
O(n) - you have to scan n elements, or a factor of n (n/2, n/4 etc) - still O(n).
answered Nov 11, 2009 at 7:05
Traveling Tech Guy
27.9k25 gold badges117 silver badges167 bronze badges
Comments
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. :)
Comments
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?
Comments
You have to traverse the whole array. So the complexity would be O(n).
Comments
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)
