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

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

• $d_1$ cannot be equal to $-1$, since it must be a natural number. – user99557 Jan 27 '19 at 13:33
• @akathemix: Whoops, my bad.. Since $T_{\text{findMax}(n)}$ is the "number of computation steps" and not number of comparisons or such, you can just set it to $0$ or $1$, works too. Is the second answer clear? – KVN Jan 27 '19 at 16:12