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;
}
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments