1
$\begingroup$

I have a question regarding the following sentence:

So we can make the following expressions:

The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$

The worst case running time of LINEARSEARCH is a linear function of $T(n)=an + b$ OR $Θ(n)$

Merging them together, the running time of LINEARSEARCH is no more than some constant times $n$

There is reference to some constant, what is the point of this constant? Why is not just that the running time is $n$?

What is the some constant and why does it need to be taken into consideration?

$\endgroup$
1
$\begingroup$

What is the running time of an algorithm? To answer this question, we need to specify an exact computation model with a cost for each operation. Whatever computation model you choose to use, it is highly unlikely that the running time of an algorithm on an input of size $n$ is exactly $n$. It is far more likely to be of the form $an+b$ for some constants $a,b$, and even more likely to vary a bit with the exact input, but to be bounded by some expression such as $an+b$.

As an example, consider the following algorithm for computing the maximum of an array $A[1],\ldots,A[n]$:

max = A[1]
for i = 2, ..., n:
  if A[i] > max:
    max = A[i]
return max

Let us convert it into "machine instructions":

      max = A[1]                 (1)
      i = 2                      (2)
LOOP: if i>n, jump END           (3)
      if A[i]≤max, jump CONT     (4)
      max = A[i]                 (5)
CONT: i = i + 1                  (6)
      jump LOOP                  (7)
END:  return max                 (8)

Let's assume that each line costs $1$ time unit (this is a quite arbitrary assumption). How much time does the algorithm take on an input $A$ of length $n \geq 1$?

Lines $1,2,8$ run once. Line $3$ runs $n$ times each. Lines $4,6,7$ run $n-1$ times each. Line $5$ runs once per "left-to-right record" of $A$ beyond $A[1]$, which can be any number of times between $0$ and $n-1$. In total, the running time is between $3+n+3(n-1)$ to $3+n+4(n-1)$, that is, between $4n$ and $5n-1$.

If we choose a different cost model, we will likely get a different running time. However, this running time will likely still be $O(n)$. This is why big O notation is so useful – it hides such details.

$\endgroup$
5
  • $\begingroup$ Ok so I think I get it! I am using the RAM model for this and what confused me is that no matter how many constant time operations there are (like in your example) the output is still O(n) which made me wonder why we even bother using the constant value at all as it seems to clutter up the equations. $\endgroup$ – pac234 Nov 18 '20 at 8:36
  • $\begingroup$ I guess one thing I am still unclear on now is why it is between 4n and 5n -1, how is it that 3 + n + 3(n -1) ends up actually being 4n? $\endgroup$ – pac234 Nov 18 '20 at 8:43
  • $\begingroup$ The point of big O notation is that we hide these constant factors away. You shouldn't be seeing them. $\endgroup$ – Yuval Filmus Nov 18 '20 at 8:48
  • $\begingroup$ Could I ask one more thing, why "Line 3 runs n times each`? Why is that also not n - 1? As the loop counter starts at 2 and skips the first item in A. $\endgroup$ – pac234 Nov 18 '20 at 12:05
  • $\begingroup$ Suppose $n = 1$. Then line 3 runs once. $\endgroup$ – Yuval Filmus Nov 18 '20 at 12:08

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.