Counting the steps of an algorithm for an upper bound

Question

I know that If I have a for loop, and a nested for loop, which both iterate 1 to n times, I can multiply the run times of both loops to get O(n^2). This is a clean and simple calculation. However, if you had iterations like so,

n = 2, k = 5

n = 3, k = 9

n = 4, k = 14

where k is the number of times the inner for loop iterates. At one point, it is larger than n^2, then it is exactly n^2, then it becomes less than n^2. Assuming you cannot determine k based on n, and maybe even having these points of n very far apart how do you calculate Big-O?

I tried graphing points. And at one point, I could say it was O(n^3) since some points exceed n^2, and further down, it would be O(n^2). Which one should I choose?

Answer 1

You state in your question that k is:

"... At one point, it is larger than n^2"

This is the uncertainty (or non-specificity) in your question that makes it hard to answer rigorously. Anyway, for the remainder of this answer, we shall assume that what you mean by the quote above is that:

For all values of n, the value of k(n) is bounded from above by C·n^2, for some constant C>0.

From here on, let's refer to this statement as (+).

---

Now, since you're mentioning Big-O notation, we'll proceed to somewhat loosely define what this actually means:

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

I.e., Big-O notation is a way to describe an upper bound here for the asymptotic (limiting) behaviour of our algorithm. You write in your question, however, that:

"And at one point, I could say it was O(n^3) since some points exceed n^2, and further down, it would be O(n^2)"

Now this is a very specific analysis of how the inner loop of your algorithm behaves for specific values of n, and really not something that is related to asymptotic analysis (or Big-O notation). We're not interested in specifics about how the algorithms behaves for specific values of n, but whether we can find some general upper bound for the algorithm given n is "sufficiently large" (n ≥ n0 for some constant n0).

Now, with these comments above, we can proceed to analysing the asymptotic behaviour of your algorithm.

---

We can approach this using Sigma notation, making use of statement (+) above, k(n) < C·n:

The last step (++) follows from the definition of Big-O-notation, that we loosely stated above.

Hence, given that we interpret your information regarding k as (+), your algorithm runs in O(n^3) (which is an upper bound, not necessarily a tight one).