[Algoritmi] Valutazione Worst-Case

[HeroGian]

Salve a tutti, apro questo topic per chiedere un consiglio riguardo al seguente esercizio:

"Si scriva una procedura che dati in input un array A di interi, restituisce un array B che contiene tutti gli elementi di A in copia unica. Si valuti il worst-case dell'algoritmo proposto."

CopiaUnica(A)
  k <-- max(A)  //ritorna il massimo nell'array A
  for i <-- 1 to k
      C[i] <-- 0
  for i <-- 1 to Length[A]
    idx <-- A[i]
    if C[idx] = 0 then
      C[idx] <-- 1
      B[Length[B]] <-- A[i]
      Length[B] <-- Length[B]+1
  return B

Come costo computazionale dovrebbe essere O(n).. ma non capisco come analizzare il worst-case, penso che si comporti in modo uguale per qualsiasi input..

[Alhazred]

Lo credo anch'io.
Qualunque sia l'input, l'array di partenza viene sempre letto completamente una ed una sola volta.

Questo è uno di quegli algoritmi in cui tutti i casi coincidono e la sua complessità è Θ(n).

[HeroGian]

Originariamente inviato da Alhazred
Lo credo anch'io.
Qualunque sia l'input, l'array di partenza viene sempre letto completamente una ed una sola volta.

Questo è uno di quegli algoritmi in cui tutti i casi coincidono e la sua complessità è Θ(n).

Ok, grazie mille per la risposta!