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)$?
Please try to keep your answer simple and clear :) Thank you!
Assume that $n>5$ (for looking at big $O$ notation, you can always assume such things)
The inner
count:=count + 1will 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 outercount:=count +1will 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)$$