title: Time complexity analysis in finding index of smallest element in an array-worst,average and best case
body: <pre><code>int j = 0;
  for(int i = 0; i &lt; n; ++i) {
      while(j &lt; n &amp;&amp; arr[i] &lt; arr[j]) {
          j++;
      }
  }
  </code></pre>
  
  <p>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).</p>
  
  <p><strong>Question 1:</strong> 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) ?</p>
  
  <p>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).</p>
  
  <p><strong>Question 2:</strong> How can i derive average case?</p>