CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Willyawan Maulana
Willyawan Maulana

Reputation: 11

Time complexity at finding the biggest element in array

what is the best case and average case (time complexity) in the case of Finding the biggest element on array?

i have confusing, because i compared this algorithm with sequential search and the worst case are same (O(n)) but i guess the best case and average case are different because in algorithm of finding biggest value in array we must compared all element and at algorithm of sequential search it will stop if the values was found. that means the best case is different if i use the same array in that two program but i have the biggest value at first element? but how it can be happen when we have the same worst case?

Upvotes: 1

Views: 326

Answers (1)

user1196549
user1196549

Reputation:

For the sequential search, the best case is 1 comparison and the worst n comparisons (for a uniform distribution, the expected case is (n+1)/2). In fact the number of comparisons equals the 1-based index of the searched element (n if absent).

For the search of the maximum, n-1 comparisons in all cases as you must look at all values.

If the list is sorted increasingly, a binary search finds an element in O(log n) comparisons. And returning the maximum takes 0 comparisons as it is known to be the last element.

Upvotes: 0

Related Questions