How can I find Big-O notation for my loops?

Question

I am having trouble finding out the Big-O notation for this fragment of code. I need to find the notation for both for loops.

public static int fragment(int n)
{
  int sum = 0;

  for (int i = n; i >= 1; i /= 2)
  {
    for (int j = 1; j <= i; j *= 3)
    {
      sum++;
    }
  }

  return sum;
}

Answer 1

Think of the two loops separately:

First lets consider for(int i=n; i>=1; i/=2) on each iteration the value of i will be divided by 2 until it reaches a value less than 1. Therefor the number of iterations N will be equal to the number of times you should divide i by 2 before it gets less than 1. There is a well known function representing this number - log(n).

Now lets consider the inner loop. for(int j=1;j<=i; j*=3). Here you multiply j by 3 until it becomes more than i. If you think a bit this is exactly the same number of iterations that the following slight modification of the first cycle would do: for(int j=i; j>=1; j/=3). And with exactly the same explanation we have the same function(but with a different base - 3). Problem here is that the number of iterations is depending on i.

So now we have total complexity being:

log₃(n) + log₃(n/2) + log₃(n/4) ... + log₃(1) =

log₃(n) + log₃(n) - log₃(2) + log₃(n) .... - log₃(2^log₂(n)) =

log₃(n) * log₂ (n) - log₃(2) - 2 * log₃(2) - ... log₂(n) * log₃(2) =

log₃(n) * log₂ (n) - log₃(2) * (1 + 2 + ... log₂) =

log₃(n) * log₂ (n) - log₃(2) * (log₂(n) * (log₂(n) + 1)) / 2 =

log₂ (n) * (log₃(n) - log₃(2) * (log₂(n) + 1) / 2) =

log₂ (n) * (log₃(n) - (log₃(n) + log₃(2)) / 2) =

(log₂ (n) * log₃(n)) / 2 - (log₂ (n) * log₃(2)) / 2

Calculation is bit tricky and I use a few properties of logarithm. However the final conclusion is that the cycles are of the complexity O(log(n)^2)(remember you can ignore base of a logarithm).

Answer 2

To formally infer the time complexity, using sigma notation is a suitable approach:

WolframAlpha helped me to with summations closed-form formulas.

For logarithms, you may check the last slide of this document, where Dr. Jauhar explains the logarithmic loops.