The answer is o(N) but I think answer should be o(n*log(N)).Please help.
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
The answer is o(N) but I think answer should be o(n*log(N)).Please help.
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
loops will iterate roughly n times so it can be said as O(N).
For the 1st iteration of the outer loop, the inner loop runs from j=0 to j=N-1, that is N times. Similarly for the 2nd iteration of the outer loop, the inner loop runs N/2 times.
Therefore, the inner loop runs for a total of
N + N/2 + N/4 + … times
Since this forms an infinite GP series, the inner loop runs for a total of N/(1-1/2), that is 2N times, giving you an order of growth of O(N).
outer loop have time comlex of log(n) as i =i/2 (getting halved)not i++ so how it can be n ??
but outer loop should run log(n) times as i is getting halved ,it is not i++???
[/quote]
You can say this is O(N*log(log(N))).
P.S - Correct me if I am wrong.
O(N\times \log(\log N)) is an upper bound for the code, but O(N) is tighter and, so, better
@ayush29azad: @saarthak_1607 has given the correct answer, but here is more detail: “GP” is “Geometric Progression”, and the sum he has provided is a well-known one.
thank you ,now i have understood ;