0
$\begingroup$

If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop?

I am trying to figure out the correct answer to this question for my upcoming exam. My reasoning is that if the body of the loop is executed $n-1$ times and its complexity is $n$ then the complete loop should have time complexity of $O(n \times (n-1)) = O(n^2 - 2) = O(n^2)$.

However, the correct answer given to us is $O(n^3)$. Am I missing something or is it just a mistake in the answers?

Edit: It turns out that the answer given to us was just wrong...

$\endgroup$
  • 1
    $\begingroup$ Your question is vague and it requires more detail. $\endgroup$ – aaag Feb 21 '18 at 16:11
  • 1
    $\begingroup$ Geez, who hands out such exercise problems? Learning value near zero... $\endgroup$ – Raphael Feb 21 '18 at 21:20
  • $\begingroup$ Note that O(n²) and O(n³) are not contradictory. Do you want to use $\Theta$? $\endgroup$ – Raphael Feb 21 '18 at 21:20
0
$\begingroup$

As mentioned, the body of the simple loop is run in $O(n)$. As a loop iterates over the body $n$ time (probably), the time complexity of the loop is $O(n^2)$. When you run the loop $n-1$ times, the time complexity would be $O(n^3)$.

$\endgroup$
  • $\begingroup$ The answer they gave us was just wrong but your explanation is good too so I will accept it as an answer. Thank you :) $\endgroup$ – DobromirM Feb 21 '18 at 20:22
  • 1
    $\begingroup$ Where do you get "a loop iterates over the body $n$ times" from? That's not in the question at all. $\endgroup$ – David Richerby Feb 21 '18 at 20:35
  • $\begingroup$ @DavidRicherby as I've mentioned probably! It was just a guess. $\endgroup$ – OmG Feb 21 '18 at 20:45

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.