Best/worst case of finding minimum element in an array

Question

I am trying to find the minimum element in an array, and I've been asked to figure out the number of comparisons needed while using the naïve approach. So the code I've written is:

int findMin(int arr[], int size) {
    int comparisons = 0;
    int temp = arr[0];
    for (int i = 1; i < size; i++) {
        comparisons++;
        if (arr[i] < temp) {
            temp = arr[i];
        }   
    }
    return comparisons;
}

Doesn't this require n-1 comparisons in all cases? Because I'll have to check all elements from arr[1] to arr[arr_length-1], and best case/worst case doesn't come into play as I don't know if the element is minimum unless I encounter all the elements of the array atleast once. Thus, it always does n-1 comparisons to get to the minimum element right?

One of my friends says its going to be 2(n-2)+1 worst case and n-1 best case but I don't know how that is? Am I wrong or is something else going on here?

Thaiminhpv · Accepted Answer · 2022-11-12 09:24:20Z

1

With the unsorted array, since it don't have any information about the order of the unseen element, it have to look at them all, hence the time complexity is n-1.

Your algorithm requires n-1 comparisons in all cases, which means n-1 in the worst case and also n-1 in the best case. There are no optimal inputs or pessimal inputs of your function.

FYI: What is the best, worst and average case running times of an algorithm?

answered Nov 12, 2022 at 9:24

Thaiminhpv

4144 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Techie5879 Over a year ago

Yes thats what I was thinking. Without a sorted input, I wouldnt be able to break ahead of the end of the array, until my algo has seen all elements of the array

Collectives™ on Stack Overflow

Best/worst case of finding minimum element in an array

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related