How to calculate the complexity of a given code

Question

Function(int n)
if(n<=2)
 return 1;
for(i=n ; i>n/8 ; i-=n/2)
 for(j=n ; j>2 ; j=j/2)
  syso();
return Function(n/2);

In order to calculate I have done the following : T(n) = T(n/2) + O(1) + 2logn

• T(n/2): the recursive call to the function.
• O(1) : the if statement.
• 2logn: the first "for" will run only 2 times * (the second "for") that will run logn times.

** I have assumed that the second for loop will divide the j by 2 meaning that I will have j/2^k times iterations = logn.

With the same logic the next step: T(n) = (T(n/2^2) + O(1) + 2logN)+O(1) + 2logn Keep on going until the K step: T(n) = T(n/2^k) + O(1) + 2*klogn

From the first "if" statement the function will stop when n <= 2, therefor:
n/2^k =? 2 > k = log(n) - 1.

Now I place the k in the function and I get: T(n) = T(2) + O(1) + 2(logn)^2 - 2logn We know that T(2) = O(1) as it's only doing the "if" statment.

T(n) = O(1) + 2(logn)^2 - 2logn. Assuming all the steps I've done are correct, is the complexity is O((logn)^2)?

Or I have a mistake in my calculations.

Answer 1

You can use a sample program to count how many times the inner loop is called for various values of n. Running the program below, it looks like the complexity is ~ 2*log(n)^2.

package example;    
public class Example1 {
  public static void main(String[] args) {
    int c=4;
    for (int i=0;i<20;i++) {
      new FunctionOpsCount(c).dump();
      c=c*2;
    }
  }
}

class FunctionOpsCount {
  int ops;
  private int n_;

  FunctionOpsCount (int n) {
    this.n_=n;
    f(n);
  }

  private int f(int n) {
    if(n<=2)
      return 1;
    for(int i=n ; i>n/8 ; i-=n/2)
      for(int j=n ; j>2 ; j=j/2)
        incrementOp();
    return f(n/2);
  }
  private void incrementOp() {
    ops++;
  }
  void dump() {
    System.out.printf("n=%d ops=%d 2*log(n)^2/ops=%f%n", n_, ops, 2.*Math.log(n_)*Math.log(n_)/ops);
  }
}

and it prints:

n=4 ops=2 2*log(n)^2/ops=1,921812
n=8 ops=6 2*log(n)^2/ops=1,441359
n=16 ops=12 2*log(n)^2/ops=1,281208
n=32 ops=20 2*log(n)^2/ops=1,201133
n=64 ops=30 2*log(n)^2/ops=1,153087
n=128 ops=42 2*log(n)^2/ops=1,121057
n=256 ops=56 2*log(n)^2/ops=1,098178
n=512 ops=72 2*log(n)^2/ops=1,081019
n=1024 ops=90 2*log(n)^2/ops=1,067673
n=2048 ops=110 2*log(n)^2/ops=1,056997
n=4096 ops=132 2*log(n)^2/ops=1,048261
n=8192 ops=156 2*log(n)^2/ops=1,040982
n=16384 ops=182 2*log(n)^2/ops=1,034822
n=32768 ops=210 2*log(n)^2/ops=1,029542
n=65536 ops=240 2*log(n)^2/ops=1,024966
n=131072 ops=272 2*log(n)^2/ops=1,020963
n=262144 ops=306 2*log(n)^2/ops=1,017430
n=524288 ops=342 2*log(n)^2/ops=1,014290
n=1048576 ops=380 2*log(n)^2/ops=1,011480
n=2097152 ops=420 2*log(n)^2/ops=1,008951

Answer 2

Here is a derivation to compliment Danielle's numerical experiment.

---

As Danielle's comment points out, the outer loop only executes twice, once with i = n and once i = n/2. The inner loops don't depend on i which makes things easier.

The loop over j will run precisely floor(log2(n)) times, so, assuming that syso() is O(1):

i.e. your recurrence relation is correct, but the expansion was not.

Applying the stopping condition n <= 2 to find the maximum value of k:

Math notes:

• A number rounded down differs from its original value by less than 1:

  floor(x) = x + O(1)
  

• The arithmetic series 1 + 2 + ... + n = n*(n+1)/2.

Applying the above points:

Which is consistent with what the numerical results indicate.