Simple "maximum value in array" and complexity calculations

Question

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!

Sounds like homework... what have you come up with so far? Hint: sorted arrays have O(1) runtime for max/min values. — Marc B
– Marc B, Commented Oct 31, 2012 at 13:56
so's simply pulling out the max/min values on any arbitrary array. — Marc B
– Marc B, Commented Oct 31, 2012 at 13:59
@MarcB the array isn't sorted. I'm not requiring a solution but some explanation for concrete answer. As for what I came up so far, I wrote in my question. — SyndicatorBBB
– SyndicatorBBB, Commented Oct 31, 2012 at 14:02
"The maximum value in an array with size of n which contains the numbers 1,2,...n with repetitions" is obviously n, isn't it? — Vovanium
– Vovanium, Commented Oct 31, 2012 at 14:16

amit · Accepted Answer · 2012-10-31 14:25:01Z

9

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

edited Oct 31, 2012 at 14:25

answered Oct 31, 2012 at 14:18

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

SyndicatorBBB Over a year ago

Wow @amit I have no words. So nicely put. Really appreciating this.

btilly Over a year ago

The "with duplicates" bit says that it is not a random permutation. Merely n random integers in the range 1..n.

amit Over a year ago

@btilly: The term permutation was wrong, but note that the caclulation did not assume permutation - it assumed uniform distribution for each element - so it (each element) has 1/n chance to be the max, and (n-1)/n not to be it. I'll correct the terminology. Thank you for your comment.

William Over a year ago

Why is the best case O(1)? You can't be certain that any one element of an array is the max without knowing what's in the rest of the array...

amit Over a year ago

@William Note that the question states that the array contains the numbers 1,2,...n with repetitions. The best case is actually: read the first element, see it's n, and return it. This is O(1).

|

nmoses · Accepted Answer · 2012-11-01 03:11:48Z

4

If there is no prior information about the array (e.g. it's sorted), then there is no worst case or best case, and You have to scan all the elements to find out the Max, and it takes O(n) times.

Also, knowing the probability distribution of getting max value for each cell is useless in general (unless it reduces your search space. e.g., If you know that only constant number of cells have non-zero probability of getting the max value, then you just need to search those cells and it takes constant time). Thus, in general

Best-case running time = Worst-case running time = average running time = O(n)

answered Nov 1, 2012 at 3:11

nmoses

635 bronze badges

Comments

Alberto Bonsanto · Accepted Answer · 2012-10-31 14:17:16Z

2

The algorithm works like this, first you select a number (in this case i select the first number of the array and pretend it is the max, then i compare it to the next number and if it is larger I take that as the new max, until i finish searching in the array), the next code is in C:

#include <stdio.h>
#define SIZE 100

typedef struct{
    int val;
    int loc;
} find;

/* Functions declaration (Prototype) */
find maxFinder( int * const a );

int main( void )
{
    int response[ SIZE ]=
       { 1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100 };

    printf( "The max number is %d located in the index %d.\n", maxFinder( response ).val, maxFinder( response ).loc );
    return 0;
}

 find maxFinder( int * const a )
 {
    /* Local Variables initialization & declaration */
    int i;
    find result;

    result.loc = 0;
    result.val = *( a + 0 );

    for( i = 1; i < SIZE; i++ ){
        if ( result.val < *( a + i ) ){
            result.loc = i;
            result.val = *( a + i );
        }
    }
    return result;
 }

edited Oct 31, 2012 at 14:17

answered Oct 31, 2012 at 14:06

Alberto Bonsanto

18.1k10 gold badges67 silver badges93 bronze badges

5 Comments

SyndicatorBBB Over a year ago

Shouldn't you use the fact the numbers are between 1... SIZE?

Alberto Bonsanto Over a year ago

SIZE is a constant value that you must declare, in my case it's 100.

SyndicatorBBB Over a year ago

In this case SIZE = n and your values are between 1...n. This is not a general case as you have shown.

Alberto Bonsanto Over a year ago

It is general case, just change SIZE value as you wish, and it searchs from 0 (first element of the array until the array finishes (n-1)

Venkat.R Over a year ago

@Alberto Bonsanto: Can you share the code in Javascript / PHP! please

japreiss · Accepted Answer · 2012-10-31 14:02:23Z

1

The worst and best cases are simple. The average case is more interesting. Look at the Wikipedia page for Geometric Distribution.

answered Oct 31, 2012 at 14:02

japreiss

11.3k2 gold badges42 silver badges79 bronze badges

2 Comments

SyndicatorBBB Over a year ago

Best case - in case it is the first element : O(1) and worst case : O(n) , is that right?

japreiss Over a year ago

Based on your comments you seem like you are confident and you understand the idea. Go with your instincts :)

krisskad · Accepted Answer · 2023-01-15 19:59:31Z

0

What if we traverse only half of the length of the array? Will it become O(n/2) time complexity?

array = [6, 8, 9, 4, 100]

l = len(array)
max = 0

for i in range(l//2):
  if max<array[i]:
    max = array[i]
  
  if max<array[-1-i]:
    max = array[-1-i]

if l%2!=0:
  if max<array[i+1]:
    max = array[i+1]

print(max)

Here Im traversing array from the both side at a time - Is it a faster solution to find max value in array or we have any better way?

answered Jan 15, 2023 at 19:59

krisskad

1089 bronze badges

Collectives™ on Stack Overflow

Simple "maximum value in array" and complexity calculations

5 Answers 5

6 Comments

Comments

5 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

6 Comments

Comments

5 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related