2
$\begingroup$

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:

Formula

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.

process

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).

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What you mean to write is probably $W(n)\rightarrow \infty$ as $n\rightarrow\infty$. This is true, but it is true for almost any non-trivial algorithm. So it does not tell a lot about this algorithm. In essence, big-O notation is more specific about what happens when $n$ is large. Have another read on what big-O notation means intuitively or formally and then look back at your question. $\endgroup$ – Discrete lizard♦ Jan 22 '19 at 21:39
  • $\begingroup$ Yes I do know big-O is better for describing worst-case, however we were asked literally "give worst-case in terms of n without using big big-O notation" and I couldn't figure it out after looking for an answer on the internet. $\endgroup$ – MikeKatz45 Jan 22 '19 at 21:43
  • $\begingroup$ "The inner loop carries out the sum operation $n \times n \times n$ times." That is not correct. Can you take a close look? $\endgroup$ – John L. Jan 22 '19 at 21:45
  • 2
    $\begingroup$ I think what was meant is to give the exact amount of times an 'elementary operation' is executed in the worse case. So, they likely want you to be more precise by giving a function such as $3\cdot n^3 + n -1$ (I made that up, this is likely not your answer). $\endgroup$ – Discrete lizard♦ Jan 22 '19 at 21:45
  • $\begingroup$ @Apass.Jack oh dang I didn't pay attention to this example's loops (in class we used a different one), is it 2n instead? $\endgroup$ – MikeKatz45 Jan 22 '19 at 22:00
2
$\begingroup$

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$-notations. We can say the computation cost is $\Theta(n^3)$ under a set of very general assumptions (a.k.a. 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
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I actually did this for another question regarding the same exercise asking "What is the output value of r? Express your solution in terms of n". I was able to do what you did successfully but I never made the connection of the resulting function with time complexity since that function only describes the value of r when provided a certain n. To my understanding a time complexity function describes the time the algorithm takes to run and not the output itself. $\endgroup$ – MikeKatz45 Jan 22 '19 at 23:00
  • $\begingroup$ By sheer luck or by design, it happens the value of $r$ at the end of each loop is the number of times the innermost loop executed so far. $r$ is 0 initially. Every time the innermost loop executed, $r$ increases by 1. $\endgroup$ – John L. Jan 22 '19 at 23:01
  • $\begingroup$ Ok so my iniitial statement was correct? The inner loop executes n x n xn (In asymptotic terms, that is ignoring constants and lower degree terms) $\endgroup$ – MikeKatz45 Jan 22 '19 at 23:08
  • $\begingroup$ If you meant n x n x n times asymptotically ignoring a constant factor, you were correct. Sorry that I was not able to understand it that way. $\endgroup$ – John L. Jan 23 '19 at 0:05
  • $\begingroup$ don't worry about it, I edited the question a little bit with the reason why I think that function is not the time complexity. $\endgroup$ – MikeKatz45 Jan 23 '19 at 0:28

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.