-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
Improve this question
$\endgroup$
10
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 19:34

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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