Time complexity: O (logN) or O (N)?
I thought the time complexity of the following code was O (log N), but the answer says it is O(N)
. I wonder why:
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
For inners for-loops, this is done multiple times:
N + N/2 + N/4 ...
it seems to me that logN
. Please help me understand why here. Thanks to
+3
source to share
2 answers
1, 1/2, 1/4, 1/8 ... 1/2 ** n is a geometric sequence with a = 1, r = 1/2 (a is the first term, and r is the general relation).
Its amount can be calculated using the following formula:
In this case, the sum limit is 2, so:
n + n/2 + n/4 ... = n(1 + 1/2 + 1/4...) -> n * 2
So complicity is O (N)
+6
source to share
