for (i = 2; i < n; i = i * i) {
for (j = 1; j < i / 2; j = j + 1) {
sum = sum + 1;
}
}
I know that the outer loop can run for a maximum of $n^2$ times and the inner loop will run for $\frac{n^2}{4}$ times.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThe second loop runs in $O(i)$. The first loop goes over the powers $2^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is $$ O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}), $$ where $m$ is the maximal integer such that $2^{2^m} < n$. We can bound $$ 2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} < 2n. $$ Therefore the overall running time is $O(n)$.
In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log_2 \log_2 (n-1) \rfloor}})$, with a bit more work.
Since $i$ iterates in powers of $2$ to reach a value $n$. The average complexity will be $log_{2}(n)$ only for outer loop.
But when $i$ = $2$ ,its value will raise in terms of powers of $2$ .The same will be true for inner loop iterations(Let's just ignore the divided by $2$ factor since $2$ is a constant). The total running time in terms of number of iterations of inner loop can be summed as
$i^1 + i^2 + i^3 + \cdots + i^{log_{2}(n)}$
OR
$2^1 + 2^2 + 2^3 + \cdots + 2^{log_{2}(n)}$.
But for any positive integer $x,$ $2^1 + 2^2 + 2^3 + \cdots + 2^{x-1}= 2^{x}-2$. So the total number of steps will be
$2*2^{log_{2}(n)}-2$
Now because $2^{log_{2}(n)}=n$ we can write the number of steps as
$2n-2$
Ignore all constants you get the complexity $O(n)$
You are asking for asymptotic complexity. O(n) is obviously an upper bound. However, for every epsilon there are plenty values of n that execute in less than n * epsilon steps, so that upper bound is quite useless. “N^2/4” is way off the mark. For example, for 257<= n<= 65536, there are only about 256 steps, far less than n.
Let f(n) = floor (log(log(n))), where log is the base 2 logarithm. Let g(x) = 2^(2^x)), then the asymptotic complexity is $\Theta(g(f(n))$
PS. Yuval is right, it’s floor(log(log(n-1)), not n.
sum
at the end of the code? The printout will be the number of times the inner loop has been executed. Check whether it is expected, for example, when you set $n=10^6$. $\endgroup$