# Approximating the runtime of a practice problem [duplicate]

I'm studying for an algorithms exam and came upon the problem :

    for (i = 0; i < n * n; i++) {
i++;
for (j = 0; j < (log(n) * log(n) * log(n)); j++) {
j++;
}
}


I figure that line 1 costs $c_1(n^2)$, line 2 costs $c_2(n^2 - 1)$, line 3 costs $\sum_{j=0}^{n^2} \log(j)^3$, and line 4 costs $\sum_{j=0}^{n^2} \log(j)^3 - 1$. Am I on the right track? If so, what do the summations get simplified to?

• What division by two? – David Richerby Oct 15 '16 at 17:06
• I can't tell which track you are on, so I can not tell you if it's the right one. How did you get to these results? – Raphael Oct 17 '16 at 8:25
• I think you have some off-by-ones there. – Raphael Oct 17 '16 at 8:26

Those lines with the increments matters for the final complexity function, but do not take them in count as it will only make things messy. The function can be simplified as follow:

The outer for runs $\frac{n^2}{2}$ times, and for each of it's iterations it runs $\frac{log^3{n}}{2}$ times.

We can call the complexity function $T(n) = \frac{n^2}{2} * log^3{n}$ which leads to $O(n^2 log^3{n})$.

• Each iteration runs log^3 (n) / 2 times :-) Same strange code in both loops. – gnasher729 Oct 15 '16 at 16:16
• The division by 2 comes from the fact that the counters are being incremented twice, correct? – Batman Oct 15 '16 at 19:55
• Exactly. j must become as large as $log^3 n$ but is increased twice per iteration; any decent compiler will combine that into one operation. Having j++ in your loop statement and in the body of the loop is likely to be a bug; it's rarely useful. – gnasher729 Oct 16 '16 at 11:11
• The question states nowhere that we are interested only in $O$-bounds. – Raphael Oct 17 '16 at 8:24

(Original question started with for (i = 0; i = n*n; ...) ) The runtime is zero if n = 0, and the algorithm runs forever otherwise.

• Even with i == n*n, I don't see why it should run forever. For n == 0 it would perform one iteration of the outer loop (and crash because log(0) is not defined), for all other n it would halt immediately (after constant, not zero time). – Raphael Oct 17 '16 at 8:23