Lecture Notes on Asymptotic Notation

Overview

This lecture focuses on different asymptotic notations used to describe the time complexity of algorithms. The discussion includes Big O (O), Omega (Ω), and Theta (Θ) notations, with examples for various functions and their complexities.

Key Asymptotic Notations

Big O Notation (O)

• Describes the upper bound of an algorithm's running time.
• Represents the worst-case scenario.

Example:

• Function: 2n^2 + 3n + 4
  • Big O: O(n^2) since 2n^2 + 3n + 4 <= 9n^2 for large values of n.
  • F(n) ≤ c * G(n) for some constant c and sufficiently large n.

Omega Notation (Ω)

• Describes the lower bound of an algorithm's running time.
• Represents the best-case scenario.

Example:

• Function: -n^2 + 3n + 4
  • Omega: Ω(n^2) since -n^2 + 3n + 4 >= 1 * n^2.
  • F(n) ≥ c * G(n) for some constant c and sufficiently large n.

Theta Notation (Θ)

• Describes a tight bound on the algorithm’s running time.
• Represents both the upper and lower bounds.

Example:

• Function: -n^2 + 3n + 4
  • Theta: Θ(n^2) since it lies between 1 * n^2 and 9 * n^2.
  • a * G(n) ≤ F(n) ≤ b * G(n) for constants a and b and sufficiently large n.

---

Functions and Their Complexities

Function: n^2 log n + n

• Big O: O(n^2 log n) since it is less than 10n^2 log n for large n.
• Omega: Ω(n^2 log n) since it is greater than 1n^2 log n for large n.
• Theta: Θ(n^2 log n) since it tightly bounds the function.
• Note: n^2 log n lies between n^2 and n^3.

Function: n! (Factorial)

• Big O: O(n^n) upper bound.
• Omega: Ω(1) lower bound.
• No Theta because n! does not have a tight bound as it varies significantly for different ranges of n.
• n! fluctuates between O(n^n) and Ω(1).

Function: log(n!)

• Big O: O(n log n).
• Omega: Ω(1).
• No Theta due to variable growth.

---

When to Use Each Notation

• Theta (Θ): Preferred when you can find a tight bound for a function. It gives exact time complexity.
• Big O (O): Useful to indicate an upper limit of runtime; often used when a precise runtime is hard to ascertain.
• Omega (Ω): Indicates a lower limit; helpful when knowing the minimum performance of an algorithm.

Advice: Prefer using Theta (Θ) for exact complexity when possible.

Example Analogy

Think of these notations like estimating the price of a mobile phone:

• Theta (Θ): Exact expected price (e.g., an average market price).
• Big O (O): Maximum possible price (e.g., premium models).
• Omega (Ω): Minimum possible price (e.g., budget models).
• Theta is most useful as it gives an accurate representation, while Big O and Omega provide bounds.

Conclusion

Understanding and applying these notations correctly can greatly assist in analyzing and optimizing algorithm performance in computer science.

Next: Properties of asymptotic notations (covered in the next video).