Big Oh(O) vs Big Omega(Ω) vs Big Theta(θ) notations | Asymptotic Analysis of Algorithms with Example

Support Simple Snippets by Donations -
Google Pay UPI ID - tanmaysakpal11@okicici
PayPal - paypal.me/tanmaysakpal11
--------------------------------------------------------------------------------------------- In this tutorial we will understand the 3 different Asymptotic Time Complexity analysis of Algorithms namely -
Big Oh(O)
Big Omega(Ω)
Big Theta(θ)
We will understand each Complexity by taking its mathematical definition as well as example with graph.
Lastly we will understand its practical usage & understand why we really need 3 different time complexity measures.

Big O notation -
Big O notation specifically describes worst case scenario.
It represents the upper bound running time complexity of an algorithm.
Mathematically -
Let f and g be functions of n - where n is natural no denoting size or steps of the algorithm then -
f(n) = O(g(n))
IFF
f(n) less than or = c.g(n)
where n greater than = n0, c greater than 0, n0 greater than = 1

Big Omega notation -
Big Omega notation specifically describes best case scenario.
It represents the lower bound running time complexity of an algorithm.
Basically it tells you what is the fastest time/behavior in which the algorithm can run.
f(n) = Ω(g(n))
IFF
f(n) greater than or = c.g(n)
where n greater than = n0, c greater than 0, n0 greater than = 1

Big Theta (θ) notation -
Big Omega notation specifically describes average case scenario.
It represents the most realistic time complexity of an algorithm.
f(n) = θ(g(n))
IFF
c1.g(n) less than or = f(n) less than or = c2.g(n)
where n greater than = n0, c1,c2 greater than 0, n greater than = n0, n0 greater = 1

Big Ω - Best Case
Big O - Worst Case
Big θ - Average Case


Simple Snippets Official Website -
http://simplesnippets.tech/
Simple Snippets on Facebook -
  / simplesnippets  
Simple Snippets on Instagram -
  / simplesnippets  
Simple Snippets on Twitter -
  / simplesnippet  
Simple Snippets Google Plus Page -
https://plus.google.com/+SimpleSnippets
Simple Snippets email ID -
[email protected]

For More Technology News, Latest Updates and Blog articles visit our Official Website - http://simplesnippets.tech/