Running Time for Finding Maximum

Question

Consider the algorithm findMax that finds the maximum entry in an integer array.

Algorithm findMax($A$)
Input: An integer array $A$
Output: The maximum entry of $A$

1. m <- A[0]  
2. for i <- 1 to A.length - 1 do  
3.     if A[i] > m then  
4.        m <- A[i]  
5. return m

1. Show that there are constants $c_1,d_1,c_2,d_2 \in \mathbb{N}$ such that $c_1n + d_1 \leq T_{findmax(n)} \leq c_2n + d_2$ for all $n$, where $n$ is the length of the input array.

2. Argue that for every algorithm A for finding the maximum entry of an integer array of length $n$ it holds that $T_A$$(n)$ $\geq n$.

NOTE: The (worst-case) running time of an algorithm A is the function $T_A: \mathbb{N} \rightarrow \mathbb{N}$ where $T_A$$(n)$ is the maximum number of computation steps performed by $A$ on an input of size $n$.

---

1. My intuition was that $c_1$ and $c_2$ correspond to the number of times the next element of the array is greater than the current maximum, but I don't see how to fit it in the equation.

1 - executed $1$ time
2 - executed $n$ times
3 - executed $(n-1)$ times
4 - executed $c$ times - - - best case: $0$ times / worst case: $(n-1)$ times
5 - executed $1$ time

In the total sum of steps:

• Step 1 + Step 5 = 2 times
• Steps 2,3,4 $\leq 3n$ times

Therefore, $c_1 = 1$, $d_1 = 2$, $c_2 = 3n$, $d_2 = 2$.

2. For the second question, would it be enough to show that the best-case scenario (array sorted in non-increasing order) takes at least $n$ steps?

Answer 1

Question 1

I think you are overcomplicating things, the question is about $\mathcal{O}$-notation, you don't need any meaning attached to these constants. Try making your life easy and pick simple ones:

You only need a lower bound, so just set $c_1 = d_1 = 1$, clearly $n + 1 \leq T_{\text{findMax}(n)}$.

Similarly you only need an upper bound, set $c_2 = 4$ and $d_2 = 42$, giving you $4n + 42 \geq T_{\text{findMax}(n)}$.

Question 2

It's not clear how $T_A$ is defined, so it's hard to answer Question 2.

Assume there is an algorithm $A$ with $T_{A(n)} = t < n$. So this algorithm is restricted to read/compare at most $t$ elements of $a_1,\dots,a_n$ and therefore there is always a sequence $a_1,\dots,a_n$ where the algorithm will fail, ie. the actual maximum is not among the $t$ elements. $\Rightarrow\!\Leftarrow$