While calculating the largest number in a given array of size n, you would need a variable like largestNumberSoFar. You will keep updating largestNumberSoFar as and when you find a number larger than previously seen. Roughly, how many times would you need to update this variable?
This is a probability question. All numbers appear with equal probability in the array. Crudely, I can visualise that the rate of number of replaces will exponentially reduce as we progress towards the end of the array (as the probability of a number higher than previously seen would keep on decreasing) but can it be shown via a probability equation?
There can be 2 further variations based on types on numbers in the array:
- Infinite number set (from -infinity and +infinity)
- Finite number set
Will the answers change?
Suppose that there is a random array of $k$ integers. The probability that the last element is greater than the rest of the array is $\frac{1}{k}$. Using this fact and going through the array gives that the expected number of times that you will update your variable is $$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$where $n$ is the length of your array. This is very close to $\ln (n)$ for large $n$ so the answer you are looking for is $\boxed{\ln (n)}$.