The trio of asymptotic complexity (O, Ω, θ):
1-
The Big Oh “O”
f (n)=O(g(n))
reads as f on n is big oh of g of n
Eg- 5n+5=O (n) means 5n+5≤6n for all n≥5
O (1) that means a constant
O (n): linear
O (n2): quadratic
O (n3): cubic
O (2n): exponential
2- Omega “Ω”
f (n)= Ω(g(n)) reads as f of n is omega of g of n
Eg- 4n+2= Ω means 4n+2≥4n for n≥1
In the case of Oh g(n) is an upper bound on the value of f(n)
for all n, n ≥no while
statement f(n)= Ω (g(n)) states that g(n) only a lower
bound on f(n)
3- Theta "θ"
f (n)= θ (g(n)) reads f of n is theta of g of n
Here f (n) = θ (g (n))
G (n) is
both upper and lower bound on f (n.)
Comments
Post a Comment