Time Complexity of a loop iteration by i^2

user_17399032 0
Viewed 67
i=2;
while(i<n) {
   i = i*i;
   //O(1) complexity here
}

I'm new to time complexity and trying to figure out what this would be. I know that if the iteration would've been i=2*i then it'd be O(log(n)) but I don't really know how I can calculate iterations of i^2.

Intuitively it'd also be O(log(n)) because it "iterates faster" but I don't know how to formally explain this.

Any help would be appreciated, thanks in advance

time-complexity
3 Answers

You can neatly translate this into the i = 2 * i case you mentioned by considering the mathematical log of i. Pseudocode for how this value changes:

log_i = log(2);
while (log_i < log_n) {
    log_i = 2 * log_i;
    // O(1) stuff here
}

It should be clear from this that the time complexity is O(log log n), assuming constant multiplication cost of course.

user_35293230

I think it's easier to approach this problem just using mathematics.

Consider your variable i. What sequence does it take? It seems to be

2, 4, 16, 162, ...

If you look at it for a bit, you notice that this sequence is just

2, 22, (22)2, ((22)2)2, ... or

21, 22, 24, 28, ... which is

220, 221, 222, 223, ...

so general term for this sequence is 22k where k = 0, 1, 2, ...

Now, how many iterations does your loop make? It will be in the order of k when 22k = n. So let us solve this equation:

22k = n (apply log2 to both sides)

2k = log2n (apply log2 to both sides again)

k = log2(log2n)

In big-O notation, the base of the logarithm doesn't matter, so we say your algorithm has a time complexity of:

O(log log n).

user_105591420

There are different ways to do i^2, The iterative approach (The one that you have) will have a time complexity of O(N) because we are iterating once till N.

Another method is recursive, something like:

static long pow(int x, int power) {
//System.out.println(x+":"+power);
//base condition 
if (power == 0)
  return 1 l;

if (power == 1)
  return x;
power--;
return x * pow(x, power);}

this will also have a time complexity of O(N) because pow(x,n) is called recursively for each number from 1 to n.

The last method (and more efficient one) is the Divide and conquer which can improve the time complexity by only by calling pow(x, power/2).

static long pow(int x, int power) {
//System.out.println(x + ":" + power);
//base condition 
if (power == 0)
  return 1 L;

if (power == 1)
  return x;
log res = pow(x, power / 2);
//if power is even
else if (power % 2 == 0)
  return res * res;

else
  return x * res * res; //if power is odd}

The time complexity in this case would be O(log N) because pow(x,n/2) is calculated and then stored for using the same result.

user_131566810
Related