Simple "maximum value in array" and complexity calculations
algorithm, complexity-theory
Solution
Best case - finding the max element as the first (`O(1)`), worst case - it is the last element checked (`O(n)`).
The tricky part is the average case. To find the average case - we need the expected number of iterations!
Since you can stop after you find the maximum, we can split the problem into two parts:
- `[0,n-1)`: Since on average (assuming uniform independent distribution for each element) - the number `n` has probability 1/n to be in each place, then the expected number of iterations for this part is `1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n` 1 The above formula yields an ugly formula which is `O(n)`
- The last element is going to be checked if the first n-1 elements did not contain the value `n`: so you need to add to the above `n* ((n-1)/n)^(n-1)`, which is `O(n)` as well (lim to infinity is `1/e * n`).
This totals in `O(n)` average time solution.
(1): The formula for each element is `j*((n-1)/n)^(j-1) * (1/n)` because:
- `j` - for the number of elements checked (number of iterations)
- `((n-1)/n)^(j-1)` - Probability that there is no `n` in the previous elements
- `(1/n)` - Probability this number is `n`.
Problem
I'm pretty new to this stuff and I need your help. I should build an efficient simple algorithm which returns the maximum value in an array with size of n which contains the numbers 1,2,...n with repetitions. Then I have to determine the best running time, average running time and worst running time. So I have two questions: First of all I'm trying to understand what's the idea of requiring an efficient solution for this simple algorithm. As far as I understand I should only have a simple loop from 1 to n and look for the maximum value. Is the "efficient" algorithm points out that If I find the value n in the array I can stop searching more values because this is the maximum value in the array? How do I determine the best running time and average running time using the fact, while calculating the average running time, that It's a uniform distribution. That is, each cell in the array has a chance of 1/n to be the maximum value. Thanks a lot in advance!