# How is the time complexity of an algorithm with successive-nested loops measured?

Does the time complexity of the following pseudo-algorithm simplify as $O(n^2 log(n)) = O(n^2)$?

SOME ALGORITHM

GET n
FOR (i=1; i<=n; i++)
{
calculationOfN[i] // some polylogarithmic time calculation

FOR (j=1; j<=n; j++)
{
// some linear calculation
}
FOR (k=0; k<=n; k++)
{
// some linear calculation
}
// some statement
}
// some statement

• I assume by "some linear calculation", you mean "some calculation that takes constant time"? Otherwise if it is in fact a linear time calculation ($O(n)$ time), this will take O(n^3) time. Jul 23, 2017 at 18:38
• What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat?
– Raphael
Jul 23, 2017 at 19:18
• $O(n^2 log(n)) = O(n^2)$ -- that's a false statement, no matter the algorithm.
– Raphael
Jul 23, 2017 at 19:19
• You may want to check out our reference question on how to approach algorithm analysis. One of the first questions you'll have to answer is: Linear in what?
– Raphael
Jul 23, 2017 at 19:19
• @Raphael, thanks! yes, I got stuck with what's in the body of the loop and how it pertains to the algorithm itself. I still honestly am not following how successive loops within an outer loop add up as jschnel shows above. If you want to help me along though, I'd be greatly appreciative. But the loop body for each loop really is $O(n)$, linear time. The second loop involving $k$ doesn't begin until the previous loop ends. If you can help, that'd be great.
– Jeff
Jul 23, 2017 at 19:34

Assuming your linear calculations are actually constant-time calculations, then yes, the final time complexity of the algorithm will be $O(n^2)$ (but not for the reason you seem to be indicating).
Your polylogarithmic time calculation (running in time $O(\log^{k}n)$) is run $n$ times (one for each $i$); each of your secondary $O(1)$ time computations is run $O(n^2)$ times (one for each $(i,j)$ pair and $(i,k)$ pair respectively). Altogether, this leads to a time complexity of $O(n\log^{k}n + n^2)$ (notably, not $O(n^2\log^{k}n)$). Since $n^2$ dominates $O(n\log^{k}n)$, this is $O(n^2)$.