Time complexity analysis in finding index of smallest element in an array-worst,average and best case

Question

int j = 0;
for(int i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}

Here is a code for finding index of smallest element (first occurrence) in an array.And i say that the worst case would be O(n2) best case would be O(n).

Question 1: In the worst case my inner while loop does not always runs for n times,in maximum of cases it would run for 1 or 2 times with respect to outer for loop,So i assume that the inner loop runs for (n-c) times where c is some constant and outer loop runs for n times.Am i correct that the complexity would we n*(n-c) which is O(n2) ?

In the best case minimum element being at first index,my inner loop does not runs any time so the time complexity is O(n).

Question 2: How can i derive average case?

I don't understand how you find an algorithm with more that O(n). Just iterate on the array one time and take the lower element. — Stargateur
– Stargateur, Commented Jun 30, 2017 at 10:38
As @Stargateur suggests, your algorithm has a higher complexity as any searching algorithm, the inner loop is not required, try to eliminate it. Answering your second question in this link, the average case is explained properly and how to achieve it, in a nutshell, is testing the algorithm with a population based on probability distribution or random numbers. wikipedia-average-case — JTejedor
– JTejedor, Commented Jun 30, 2017 at 10:47
Yes we can make that in O(n),but i was given this code to find the time complexity.Help me find for this..!Thank You. — Sai Shankar
– Sai Shankar, Commented Jun 30, 2017 at 10:49

nemetroid · Accepted Answer · 2017-06-30 10:47:41Z

2

You start with j = 0 and never decrement j. Each iteration of the while loop increases j by one, and the while loop has the condition j < n, so the statement j++ can run at most n times, i.e. worst case O(n).

answered Jun 30, 2017 at 10:47

nemetroid

2,16914 silver badges20 bronze badges

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

1 Comment

Sai Shankar Over a year ago

Yeah Thank you. j will not exceed n at any time. So in all the 3 cases time complexity would be O(n). Right ??

BishalG · Accepted Answer · 2017-07-01 09:59:32Z

1

We can simply ignore constant while finding the Big O notation( why? ).

The program you wrote for finding index of minimum element in the array makes n iterations when array elements are in increasing order and 2*n iterations when array elements are in decreasing order. But we can simply conclude that this algorithm has overall O(n) complexity in all three cases.

answered Jul 1, 2017 at 9:59

BishalG

1,43413 silver badges27 bronze badges

Collectives™ on Stack Overflow

Time complexity analysis in finding index of smallest element in an array-worst,average and best case

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related