Little o and Little omega notations
Little-o: Big-O is used as a tight upper bound on the growth of an algorithm’s effort (this effort is described by the function f(n)), even though, as written, it can also be a loose upper bound. “Little-o” (o()) notation is used to describe an upper bound that cannot be tight.
Definition: Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is o(g(n)) if for any real constant c > 0, there exists an integer constant n0 > 1 such that 0 < f(n) < c*g(n).
Thus, little o() means loose upper-bound of f(n). Little o is a rough estimate of the maximum order of growth whereas Big-O may be the actual order of growth.
little-omega:
The relationship between Big Omega (Ω) and Little Omega (ω) is similar to that of Big-O and Little o except that now we are looking at the lower bounds. Little Omega (ω) is a rough estimate of the order of the growth whereas Big Omega (Ω) may represent exact order of growth. We use ω notation to denote a lower bound that is not asymptotically tight.
Definition : Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is ω(g(n)) if for any real constant c > 0, there exists an integer constant n0 > 1 such that f(n) > c * g(n) > 0 for every integer n > n0.
f(n) has a higher growth rate than g(n) so main difference between Big Omega (Ω) and little omega (ω) lies in their definitions.In the case of Big Omega f(n)=Ω(g(n)) and the bound is 0<=cg(n)<=f(n), but in case of little omega, it is true for 0<=c*g(n)<f(n).
Asymptotic Analysis of Algorithms Notes for GATE Exam [2024]Asymptotic Notations
This Asymptotic Analysis of Algorithms is a critical topic for the GATE (Graduate Aptitude Test in Engineering) exam, especially for candidates in computer science and related fields. This set of notes provides an in-depth understanding of how algorithms behave as input sizes grow and is fundamental for assessing their efficiency. Let’s delve into an introduction for these notes:
Table of Content
- Introduction of Algorithms
- Asymptotic Analysis
- Worst, Best and Average Case
- How to Analyse Loops for Complexity Analysis of Algorithms?
- How to combine the time complexities of consecutive loops?
- Algorithms Cheat Sheet for Complexity Analysis:
- Runtime Analysis of Algorithms:
- Little o and Little omega notations
- What does ‘Space Complexity’ mean?
- Previous Year GATE Questions