title: Why doesn't the while loop contribute O(n) to the total time complexity?
body: <p>I got this problem from <a href="https://www.interviewbit.com/problems/amortized2/" rel="nofollow noreferrer">Interview Bit</a></p>
  
  <p><strong>Problem</strong></p>
  
  <pre><code>int j = 0;
  for(i = 0; i &lt; n; ++i) {
      while(j &lt; n &amp;&amp; arr[i] &lt; arr[j]) {
          j++;
      }
  }
  </code></pre>
  
  <p><strong>Question</strong></p>
  
  <p>The total number of comparisons that the while loop does is about n (probably less than or equal to n depending on <code>arr</code>). The loop runs n times. Shouldn't the time complexity be O(n^2)?</p>