0
157
VistasTrying to understand the reason for this time complexity
I am trying to calculate the time complexity of these two algorithms. The book I am referring to specifies these time complexities of each.
A) Algorithm A: O(nlogn)
int i = n;
while (i > 0)
{
for (int j = 0; j < n; j++)
System.out.println("*");
i = i / 2;
}
B) Algorithm B: O(n)
while (n > 0)
{
for (int j = 0; j < n; j++)
System.out.println("*");
n = n / 2;
}
I can see how algo. A is O(nlogn). The for loop is O(n) and while loop is O(logn). However I am failing to see how AlgoB has a time complexity of O(n). I was expecting it to be O(nlogn) also. Any help would be appreciated.
2 Respuestas
Responde la pregunta0
Algorithm B is printing half the starts at every iteration. Assume n=10, then:
n=10 -> 10*
n=5 -> 5*
n=2 -> 2*
n=1 -> 1*
In total 18* are printed. You will print n + n/2 + n/4 + ... + n/(2^i) stars. How much does i value? It is equal to the number of steps required for n to become 0. In other terms, it is the exponent to which 2 must be raised to produce n: log_2(n). You get the sum in picture:
Which can be approximated to O(n).
0
Let's look at Algorithm B from a mathematical standpoint.
The number of * printed in the first loop is n. The number of * printed in each subsequent loop is at most n/2. That recurrence relation leads to the sequence:
n + n/2 + n/4 + n/8 + ...
If this were an infinite sequence, then the sum could be represented by the formula n/(1 - r), where r is the factor between terms. In this case, r is 1/2, so the infinite sequence has a sum of 2(n).
Your algorithm certainly won't go on forever, and it each time it loops, it may be printing less than half the stars of the previous loop. The number of stars printed is therefore less than or equal to 2(n).
Because constant factors drop out of time complexity, the algorithm is O(n).
This concept is called amortized complexity, which averages the cost of operations in a loop, even if some of the operations might be relatively expensive. Please see this question and the Wikipedia page for a more thorough explanation of amortized complexity.