# Computational complexity: what is the worst case of the following algorithm?

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$:

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

• The $O$ symbol has significance only for big $n$. When evaluating complexity you can always assume that $c/n\approx 0$ for constant $c$. – N74 Jul 5 '17 at 11:59
• 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 – AleksandrH Jul 5 '17 at 12:00

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)$$
• Thank you so much! The $k = n - 5$ in particular helped clarify this for me. – AleksandrH Jul 5 '17 at 12:18
• @AleksandrH Yeah, the main mistake you made was assume that $k$ was a constant, when in fact it was a function of $n$. – 5xum Jul 5 '17 at 12:19