Worst-case complexity in terms of n?

Question

I have this algorithm taken out from the Manual of Algorithms Analysis:

function pesky (n)
r:=0
for i:=1 to n do
  for j:=1 to i do
    for k:= j to i + j do
      r := r + 1
return (r)

I understand the time complexity of this algorithm for any given input size n > 0 will be O(n^3) since the 3 for loops will always be executed and the inner loop carries out the sum operation n x n x n times (this is of course not exact, but I say it in asymptotic terms taking out constants and lower degree terms of n); however, during a lecture we were asked to express the complexity of the worst-case in terms of n instead of in big oh notation (they left this exercise for next session).

The worst case I can think about for this algorithm would a really large integer as input n which in fact could be so large that it approaches infinity (since no restrictions for the input were stated). Even in this worst case we know time complexity would behave in O(n^3), but how would I express this "in terms of n", the best thing I could come up with is this:

But I feel like I'm just making that up and that there might be another more correct way to express it. Does anyone know the correct way to express worst-case complexity in terms of n?

EDIT: I must make it clear that I found the equation that puts n in function to the r output by means of summation resolving, however I did not consider that function as the time complexity function (and hence not the answer for "worst-case in terms of n") since that function describes output on a given input and not the time it takes to run the algorithm itself.

Moreover I had the idea to try to calculate the complexity counting each operation and I got something like this.

I am not sure if thats correct, if it is I could use that expression to state the worst-case complexity in terms of n, and also I could make my initial statement about big oh notation for the worst case more precise since this would be O(n).

Answer 1

Let us interpret for i:=1 to n inclusively. That is, i will take values $1, 2, \cdots, n$.

Let us check how many operations are done in pesky(n).

r:=0: 1 assignment.

for i:=1 to n do: $n$ assignments of i.

for j:=1 to i do: $\sum_{i=1}^ni=\dfrac{n(n+1)}2$ assignments of j.

for k:= j to i + j do: $\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ assignments of k.

r := r + 1: $\Sigma_{i=1}^n\Sigma_{j=1}^i(i+1)=\dfrac{n(n+1)(n+2)}3$ additions by 1. $\dfrac{n(n+1)(n+2)}3$ assignments of $r$.

There are $1+n+\dfrac{n(n+1)}2+\dfrac{n(n+1)(n+2)}3\cdot2=\dfrac{(n+1)(n+2)(4n+3)}6$ assignments in total.

There are $\dfrac{n(n+1)(n+2)}3$ additions in total.

If we treat the computation cost of one assignment as that of one addition, we have $\dfrac{(n+1)(n+2)(4n+3)}6+\dfrac{n(n+1)(n+2)}3=\dfrac{n(n+1)(2n+1)}2$ operations.

That is answer. Note that it is a fixed number given $n$. That is, there is no distinction of best-case, worse-case or average-case.

Or is it? If we ignore over many important details, yes. However, let us take a close look. Does for i:=1 to n do involve assignment only? Mostly like not. We have to produce 1, 2, 3, $\cdots$, n in the first place. If we produce them by addition by 1, we have $n-1$ more additions. How do we make sure we will stop when $i$ reach $n$? Probably we have to compare i with n for about $n$ times. Comparison takes time of course. We should include that cost. Wait, there is more. It is unreasonable to expect that $n$ is in the right position to be compared with $i$; We have to fetch $n$ from somewhere so that we can compare it with $i$. Now, we are not even sure how to describe that fetching and its computational cost. There are, in fact, many more important details that could be taken into consideration.

You might be wondering now. Do we have an answer or not? Yes and no.

• Yes, we have an answer, assuming some assumptions. I will not be surprised that your instructor might come up with a different number of operations under a different set of assumptions, though.
• No, the answer cannot stand up to scrutiny in many situations. That is one of the reasons why we use the big $O$-notation. We can say the computation cost is $\Sigma(n^3)$ under a set of very general assumptions (model of computation).

By the way, if you check what I had written before, you will notice and understand that I have been rather careful, saying that I am only computing how many times the innermost iteration are executed. In general, the asymptotic time complexity of a nested loop is determined by the product of that number with the average cost of one innermost iteration.

---

Here is a similar exercise for you to practice.

Exercise. Express the best-time complexity of the following function in terms of $n$ instead of in big $O$-notation. Only the operation r := r +1 is counted.

function pesky2(n)
  r:=0
  for i:=1 to n do
     for j:=1 to i do
      for k:= 1 to j do
        r := r + 1

  return (r)