Time Complexity of Programs

Question

I am just learning about time complexity, here is piece of code I've written

for (int i = 1; i <= N; i++)
  for (int j = 1; j <= N; j++)
  {
    // Spread Peace
  }

Clearly the above one is of O(N^2) complexity and its seems (for N == 1e6) to run forever.

Here is second piece of code

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j++)
  {
    // Money is Everything
  }

the above one is also O(N^2) - N*(N+1)/2 complexity is also running forever, but this code:

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j += i)
  {
    // Be my GirlFriend
  }

just executes within a sec., I am not able to derive its time complexity why this so fast? What's is the estimation for N == 1e6?

Answer 1

Let's carry out an experiment first, let's try unrolling the loop (C# implementation) and have a look what's going on:

 private static IEnumerable<String> Unroll(int N) {
  for (int i = 1; i <= N; i++) {
    StringBuilder sb = new StringBuilder();

    for (int j = i; j <= N; j += i) {
      if (sb.Length > 0)
        sb.Append(", ");

      sb.Append(j);
    }

    yield return sb.ToString();
  }

A test run with a small number (e.g. 16) reveals the picture

  Console.Write(string.Join(Environment.NewLine, Unroll(16)));

Can you see the pattern, an exponential drop? It looks like N * log(N), right?

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
2, 4, 6, 8, 10, 12, 14, 16
3, 6, 9, 12, 15
4, 8, 12, 16
5, 10, 15
6, 12
7, 14
8, 16
9
10
11
12
13
14
15
16

Now it's time for the paper and pencil: we have (for large N)

   N / 1 items (step == 1) +
   N / 2 items (step == 2) +
   N / 3 items (step == 3) +
   ...
   N / N items (step == N)
------------------------------
   N * (1 + 1/2 + ... + 1/N) = 
   N * H(N) = 
   O(N * log(N)) // Harmonic sum H(N) gives log(N)  

More accurate estimation

   H(N) = ln(N) + gamma + 1/(2*N) + ...

where

   ln()  - natural logarithm
   gamma - Euler–Mascheroni constant (0.5772156649...)

gives you for N == 1e6 about 14.4e6 loops which is, in fact, a bit overestimated; the actual count is 13970034 (14.0e6) since when aproximating with Harmonic series we did't take integer division (each k/N should be integer, i.e. not k/N, but floor(k/N)) into account.

Answer 2

You may proceed using Sigma notation:

More on Harmonic functions here: Asymptotic analysis