Tempo de execução de algoritmo

lu2535
(usa Outra)

Enviado em 18/09/2022 - 16:45h

Fiz essas duas questões em uma lista, errei, mas o professor não passou a correção

Problema da 3-soma
Entrada: Três sequência de n ∈ N valores cada a1, . . . , an, b1, . . . , bn e c1, . . . , cn em que ai, bi, ci ∈ Z para 1 ≤ i ≤ n.
Saída: A quantidade de is, js e ks tais que ai + bj + cj = 0.

Questão 1:
Considere o seguinte algoritmo:
3Soma(A, B, C)
1 m <- 0
2 for i <- 1 até n
3 do for j <- 1 até n
4 do for k <- 1 até n
5 if ai + bj + ck = 0
6 then m <- m + 1
7 return m

Calcule o tempo de processamento em função do tamanho n da entrada assumindo que:
- Cada iteração de variável toma tempo constante c1
- Cada atribuição toma tempo constante c2
- Cada soma toma tempo constante c3
- A saída toma tempo constante c4
- Cada comparação toma tempo constante c5

Questão 2: Mostre que o tempo de processamento do algoritmo 3Soma é Teta(n^3) no pior caso.