Asymptotic Notations and Functions Comparison Lecture

Logarithmic Comparison of Functions

• Simple Logarithmic Application for Comparison
  • To compare functions, apply log on both sides.
  • Example: Compare log(n bar log n) and log(2^10).
    • This becomes log(n) * log(n) and 10 * log(2) upon applying logarithmic rules.
    • log n is smaller compared to log(log n).
  • Applying log again can help identify smaller or greater functions.
  • Reducing functions via logarithms can simplify comparison.
• Example
  • Compare log(n * log_2(n)) and log(2).
  • This reduces to comparing log(n) * log(log(n)) and 1.
  • Clearly, log(n) * log(log(n)) is greater as n approaches infinity.
  • As asymptotically both would be O(n log n) and equal in growth rates.*

Coefficient Ignorance in Comparisons

• After Applying Logarithms
  • Coefficients shouldn't be ignored after applying logarithms for comparison purposes.
  • Example: Compare 2^n and n * log(n) reduced to n and log(n).
  • Comparison shows 2^n is greater asymptotically than n * log(n).

Function Comparison Examples

• Examples to Understand Comparison Techniques
  • Example: Compare G1(n) = n^3 for n < 10,000 and n^2 beyond 10,000 with G2(n) = n^2 for all n
    • Before 10,000: G1 greater than G2.
    • After 10,000: G2 becomes greater.
  • Asymptotically, G2 is greater than G1.
• Ignoring Small Coefficients for Large Values of n
  • Prefer checking large values of n, not just small values for asymptotic comparisons.

True or False Statements with Asymptotic Notations

• Analyzing Based on Asymptotic Notations
  • Example: n + k whole power m
    • Highest term would be n^m.
    • Thus, O(n^m) holds true.
  • Example: 2^n + 1 = O(2^n) since coefficient 1 is ignorable.
  • Larger powers implied larger growth rates.
  • Example:
    • Comparing log(n * log(n)) and log(n) reducing to log(n) * log(log(n)) and 1 indicating greater n terms.

Recap and Next Chapter Overview

• Review: Various Asymptotic Notation problems solved.
• Preparation for Competitive Exams
  • Practice with various problems to get adept at identifying and solving these kinds of questions.
• Next Topic: Divide and Conquer, Greedy Methods.
  • Strategies for Algorithm Analysis.