Asymptotic Analysis Big-O Notation and More by Progamiz

What is asymptotic analysis?
Asymptotic analysis is the study of change in performance of an algorithm with a change in the input size.

What are asymptotic notations?
Asymptotic notations are mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.

What are the three asymptotic notations?
The three asymptotic notations are:

  1. Big-O notation ().
  2. Omega notation ().
  3. Theta notation ().

What does Big-O notation represent?
Big-O notation represents the upper bound of the running time of an algorithm.

When is a function said to be Big-O of another function ?
A function is said to be Big-O of another function if there exists positive constants and such that for all .

Note

When you say that is , what you're saying is that the running time of will be at most or less.

What does Omega notation represent?
Omega notation represents the lower bound of the running time of an algorithm.

When is a function said to be Omega of another function ?
A function is said to be Omega of another function if there exists positive constants and such that for all .

Note

When you say that is , what you're saying is that the running time of will be at least or more.

What does Theta notation represent?
Theta notation represents the upper and lower bound of the running time of an algorithm.

When is a function said to be Theta of another function ?
A function is said to be Theta of another function if there exists positive constants , , and such that for all .

Note

When you say that is , what you're saying is that the running time of is exactly .

From ChatGPT

When analyzing algorithms using Big-O, Omega, and Theta notations, we focus on asymptotic behavior, which is how the functions behave as grows very large. Constants become insignificant because they only scale the function but don't change its fundamental growth rate.