Expected updates when finding the max

puzzle.py

#!/usr/bin/python3
"""
Simulation of the solution to a problem from a blog post by Nadbordrozd:
http://nadbordrozd.github.io/interviews/index.html
"""
from random import Random


def count_updates(x):
    """
    Count the number of updates to the "max" placeholder
    """
    max_num = x[0]
    num_updates = 0
    for i in x[1:]:
        if i > max_num:
            max_num = i    # Expected number of times this is evaluated
            num_updates += 1                                                                                                                                                                                                                                                              
    return num_updates                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                                                          
def mean(x):                                                                                                                                                                                                                                                                              
    """                                                                                                                                                                                                                                                                                   
    Calculate arithmetic mean of an array                                                                                                                                                                                                                                                 
    """                                                                                                                                                                                                                                                                                   
    return sum(x) / len(x)                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                                                          
def run_experiment(array_length, num_simulations, r=None):                                                                                                                                                                                                                                
    """                                                                                                                                                                                                                                                                                   
    Compute the mean number of updates required to find the max of an array                                                                                                                                                                                                               
    """                                                                                                                                                                                                                                                                                   
    if r is None:                                                                                                                                                                                                                                                                         
        r = Random()                                                                                                                                                                                                                                                                      
    arrays = [list(range(array_length)) for _ in range(num_simulations)]                                                                                                                                                                                                                  
    [r.shuffle(l) for l in arrays]                                                                                                                                                                                                                                                        
    return mean([count_updates(l) for l in arrays])                                                                                                                                                                                                                                       
                                                                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                                                          
if __name__ == "__main__":                                                                                                                                                                                                                                                                
    r = Random(x=42)                                                                                                                                                                                                                                                                      
    array_lengths = [10, 100, 1000, 10000]                                                                                                                                                                                                                                                
    num_simulations = 10000                                                                                                                                                                                                                                                               
                                                                                                                                                                                                                                                                                          
    print(f"Running experiments using {num_simulations} simulations")                                                                                                                                                                                                                     
    for n in array_lengths:                                                                                                                                                                                                                                                               
        print(f"Simulating solution with N={n}:")                                                                                                                                                                                                                                         
        print(f"Average updates: {run_experiment(n, num_simulations, r)}")

Output:

$ time python puzzle.py
Running experiments using 10000 simulations                                                                                                                                                                                                                                               
Simulating solution with N=10:                                                                                                                                                                                                                                                            
Average updates: 1.9184                                                                                                                                                                                                                                                                   
Simulating solution with N=100:                                                                                                                                                                                                                                                           
Average updates: 4.1979                                                                                                                                                                                                                                                                   
Simulating solution with N=1000:                                                                                                                                                                                                                                                          
Average updates: 6.5038                                                                                                                                                                                                                                                                   
Simulating solution with N=10000:                                                                                                                                                                                                                                                         
Average updates: 8.7586                                                                                                                                                                                                                                                                   
                                                                                                                                                                                                                                                                                          
real    1m31.771s                                                                                                                                                                                                                                                                         
user    1m30.248s                                                                                                                                                                                                                                                                         
sys     0m1.508s                                                                                                                                                                                                                                                                          

Apparently, the solution for an array of length n is the nth harmonic number.

For the experiment, these are:

In [1]: for n in [10, 100, 1000, 10000]: 
   ...:     print(sum(1/i for i in range(2, n + 1))) 
   ...:                                                                                                                                                                                                                                                                                   
1.928968253968254
4.18737751763962
6.485470860550342
8.787606036044384

Not too bad!