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!
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
O(n)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.