Running Time for Finding Maximum 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 &lt;- A[0]  
2. for i &lt;- 1 to A.length - 1 do  
3.     if A[i] &gt; m then  
4.        m &lt;- A[i]  
5. return m



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




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


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?
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 &lt; 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$