1
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?

Sai Shankar
  • 61
  • 1
  • 8
  • 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 Jun 30 '17 at 10:38
  • Worst case for any searching algorithm could be O(n). – haccks Jun 30 '17 at 10:41
  • 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](https://en.wikipedia.org/wiki/Average-case_complexity) – JTejedor Jun 30 '17 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 Jun 30 '17 at 10:49

2 Answers2

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).

nemetroid
  • 2,100
  • 13
  • 20
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.

BishalG
  • 1,414
  • 13
  • 24