0
$\begingroup$

Problem

The following is from a course exam of mine, and I'd like to know what I did wrong and why the correct answer (according to our professor) is $O(n)$. Note that the question states that $n > 5$:

enter image description here

My thought process

I initially put down $O(n^2)$ because I saw two nested loops and assumed this would run, in a worst-case scenario, at $O(n^2)$. The professor says it's $O(n)$.

Reflecting on the problem now, I see that the inner loop will not run for the entirety of $1$ through $n$ but only for a fraction of these iterations--only for the cases when $i < 5$. When $n = 6$, this is very nearly $O(n^2)$ because the inner loop only neglects to run for $i = 5$ and $i = 6$.

When $n = 10$, for example, the inner loop will run $n/2$ times, but the outer loop will still run all $n$ times, giving $\frac{n^2}{2}$.

More generally, I guess we could say the algorithm runs at $n*\frac{n}{k}$, but the factor of $\frac{1}{k}$ really doesn't matter when we consider the worst-case computational analysis, so it seems it's still $O(n^2)$.

Questions

What are the flaws in my thought process? How can one determine if this is in fact $O(n)$?

Please try to keep your answer simple and clear :) Thank you!

$\endgroup$
  • $\begingroup$ The $O$ symbol has significance only for big $n$. When evaluating complexity you can always assume that $c/n\approx 0$ for constant $c$. $\endgroup$ – N74 Jul 5 '17 at 11:59
  • $\begingroup$ Ah, so for $n = 1,000,000$, the inner loop will only run $4$ times, but the outer loop will run the remaining times, meaning it will dominate the inner loop in terms of complexity, correct? Is that what makes this $O(n)$, because for large $n$, it scales with the size of the input? Thanks $\endgroup$ – AleksandrH Jul 5 '17 at 12:00
3
$\begingroup$

Assume that $n>5$ (for looking at big $O$ notation, you can always assume such things)

The inner count:=count + 1 will only be performed once for $i=1$, twice for $i=2$, three times for $i=3$ and four times for $i=4$. So, all together, it will run $1+2+3+4=10$ times. Meanwhile, the outer count:=count +1 will be executed $n$ times, so all together, there are $$n+10$$ operations, an expression which is clearly $O(n)$.


In your notation, the inner loop will run $\frac{n}{k}$ times where $k=n-5$, so the total complexity is $$n\cdot \frac nk = n\cdot \frac{n}{n-5}\in O(n)$$

$\endgroup$
  • $\begingroup$ Thank you so much! The $k = n - 5$ in particular helped clarify this for me. $\endgroup$ – AleksandrH Jul 5 '17 at 12:18
  • $\begingroup$ @AleksandrH Yeah, the main mistake you made was assume that $k$ was a constant, when in fact it was a function of $n$. $\endgroup$ – 5xum Jul 5 '17 at 12:19
  • $\begingroup$ Makes perfect sense :) $\endgroup$ – AleksandrH Jul 5 '17 at 12:21

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.