Calcule as complexidades de (a) pior caso, (b) melhor caso e de (c) caso médio do algoritmo abaixo. Algoritmo M (A, n, x) Entrada: A, um vetor de n elementos, ordenado crescentemente, e x um valor. Saída: o primeiro índice do vetor A cujo elemento é maior ou igual a x. Se não houver em A elemento maior ou igual a x, o algoritmo retorna 0 (zero). { i := 1; enquanto (i ≤ n e A[i] < x) i := i + 1; se (i ≤ n) retornar i; senão retornar 0; } A complexidade deste algoritmo é função do tamanho da entrada n, mas varia também segundo a “sorte” do laço “enquanto” executar menos do que n vezes. Esta “sorte” dependerá de quais são os elementos do vetor A e qual é o valor de x. i) Pior caso: ocorrerá quando A[n] < x. Neste caso, o laço “enquanto” será executado n vezes, e sendo a complexidade deste algoritmo proporcional a esta quantidade, dizemos que T(n) = n = O(n), no pior caso. ii) Melhor caso: ocorre quando o elemento A[1] geq x. Neste caso o laço enquanto executará uma única vez e a complexidade será igual a T(n) = 1 = O(1). iii) Caso médio: nós vamos assumir uma distribuição uniforme dos casos, i.e., que todos os casos são igualmente prováveis.