I can't seem to figure out the time complexity for this algorithm. I know that the while loop will execute at O(log n) times because n keeps halving. But I'm not super sure how to represent the time complexity of the inner for loop.
while(n>0){
for(int j = 0; j < n; j++){
System.out.println("*");
}
n = n/2;
}
Each while loop divides n by 2.
Therefore, the first for loop would run n times, the second for loop would run n/2 times, the third for loop would run n/4 times, and so on.
If we set n to an arbitrary large value, then the complexity would be:
n + n/2 + n/4 + n/8 + n/16 + n/32 + ... = 2n
Of course, n is an integer, and programmatically, the division would result in 0 after enough repetitions.
Therefore, the time-complexity of the algorithm would be O(2N) = O(N)
We can figure out the complexity of both loops by inspection. For an input of n = 8, the inner loop would print out this many stars at each iteration:
8 + 4 + 2 + 1 = 15 ~ 2^4
For n = 16:
16 + 8 + 4 + 2 + 1 = 31 ~ 2^5
The complexity here is:
O(2^([log_2(N)]+1)) = 2*O(2^log_2[N])
= O(N)
We can see that at each step the number of print statements is roughly twice the value of the input N. So the overall number of print operations is actually O(N), which is linear in the actual value of the input N.
Lets n₀ be the start value of n.
At the i-th (from 0) iteration of the while loop, n = n₀ * ½ⁱ
The cost of one iteration of the while loop is n (because of the for loop)
Hence the global cost is: sum for i from 0 to whatever of n₀ * ½ⁱ
Or: n₀ times the sum for i from 0 to whatever of ½ⁱ
The sum is a sum of a geometric series, and is less than 2.
Hence the global cost is O(2.n₀) or O(n₀)
n / 2actually becomes0for anint n = 1;. In theoretical maths it will of course never become0, but in Java it does.