How can we find the time complexity for this loop

int c = 0;
int j = 1;
while (j< n^3) {
  c =1;
  System.out.println(c);
  j=j*4;
}

CodePudding user response：

Since every time j is multiplied by 4 we can say after every iteration it can be written as :

1, 4, (4^2), ..., (4^k)

Now for loop to be false, (4^k) >= n^3

4^k >= n^3
k = log(n^3) to the base 4

You can further simplify it to:

3log(n) to base 4 and remove 3 as we do for constants.

k = log(n)

This should be the complexity of your loop.