title: assess the time complexity of the following code in terms of theta
body: <p>I know the time complexity is n*log(n) , however I could only assess it with an integral for the inner loop to get an upper bound, how do I get a lower bound? to make it theta and not O?</p>
  
  <pre><code>S=0;
  for( i=1; i&lt;n; i++)
    for( j=0;j&lt;n;j+=i)
        S++;
  </code></pre>
  
  <p>so line 1 is executed once, line 2 is executed n-1 times + 1 check without entering, each one of these n-1 times line 3 is executed n/i times and we get:
  T= 1 + n + (n/1+n/2+...+n/n-1) =&lt; 1+n+n <em>(integral of 1/x from 1 to n) = 1+n+n</em>log(n) . And that's big O, how about Omega?</p>