The growth rate of T(N) is less than or equal too that of f(N)
T(N)= Ω (g(N))
The growth rate of T(N) is greater than or equal to that of g(N)
T(N)= θ (h(N))
The growth rate of T(N) equals that of h(N)
T(N)= o(p(N))
The growth rate of T(N) is less than the growth rate of p(N)
The Big O definitions are used to establish a relative order among functions. Given two functions, there are usually points where one function is smaller than the other function but it does not necessarily make sense to claim the smaller function is less than the larger one. Thus, we compare their relative rates of growth.
T(N)= Ω(𝑓(𝑁) if T(N)>=𝑓(𝑁)f(N)
Big Omega
T(N)=𝑂(𝑓(𝑁)) if 𝑇(𝑁) <= 𝑓(𝑁)
Big Oh
T(N) = θ(f (N)) if 𝑇(𝑁) = 𝑓(𝑁)
Big Theta
T(N)=o(f(N)) if T(N)<f(N)
little oh
Big oh and little oh are different because big oh allows for the possibility that the growth rates are the same.
When we say that T(N) = O(f(N)), we are guaranteeing that the function T(N) grows at a rate no faster than f(N); thus f(N) is an upper bound on T(N)
When we say that f (N) = Ω(T(N)), we say that T(N) is a lower bound on f (N).
