Pergunta

I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max.

find_max(L):
     max = -oo # negative infinity
     for k = 0 to len(L)-1:
          if L[k] > max:
               max = L[k]
     return max

However, I'm struggling to come to a solution. So far, this is what I have done:

I'm defining the sample space to be L containing values which are between 1 and 100, and having them uniformly distributed.

The worst-case running time is T(n) = n + 1 because of the initial max assignment, and the case where every element is larger than the previous one.

The best-case running time is T(n) = 2 which is the case where all elements have the same value, so there is the initial max assignment and one assignment in the for loop.

So, the running time is distributed between 2 and n+1 inclusive.

Then, the average-case running time is:

$E[t_{n}] = \sum_{2}^{n+1}$ t $\cdot$ P(t)

However, I am having difficulty defining the Random Variable T and the probability formula for values of T.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top