Notatia W (Omega mare)

Notatia W (Omega mare)

Notatia W (omega mare) precizeaza o margine asimptotica inferioara.

Pentru o functie data g(n), prin W(g(n)) se precizeaza multimea functiilor

= [2.3.4.a]

Fig. 2.3.d Reprezentarea lui f(n)=W(g)n))

• Teorema: Pentru oricare doua functii f(n) si g(n) , f(n) =
  daca si numai daca f(n) = O(g(n)) si f(n) = .[2.3.4.b]

_{Spre exemplu s-a demonstrat ca pentru orice valori ale constantelor a, b, c cu a > 0 . De aici rezulta imediat ca} .

Deoarece notatia W descrie o limita inferioara, atunci cand este utilizata
pentru a margini cazul cel mai favorabil de executie al unui algoritm, prin implicatie ea margineste inferior orice intrare arbitrara a algoritmului.