-1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jschnei Jul 23 '17 at 18:38
  • $\begingroup$ 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? $\endgroup$ – Raphael Jul 23 '17 at 19:18
  • $\begingroup$ $O(n^2 log(n)) = O(n^2)$ -- that's a false statement, no matter the algorithm. $\endgroup$ – Raphael Jul 23 '17 at 19:19
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Jul 23 '17 at 19:19
  • $\begingroup$ @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. $\endgroup$ – Jeff Jul 23 '17 at 19:34
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.