Past exam question: 2076 Baisakh (Back), Q7
Open in the Padhaiko appQuestion
What do you mean by asymptotic notation? Define Big-O notation with its properties.
Solution
Asymptotic Notation: Asymptotic notation is a mathematical notation used to describe the limiting behavior (rate of growth) of an algorithm's running time or space usage as the input size , abstracting away machine-dependent constant factors and lower-order terms.
Big-O Notation and Its Key Properties: iff there exist constants and such that for all .
Properties of Big-O:
- Constant Factor Rule: For any constant , .
- Sum Rule (Dominant Term): If and , then .
- Product Rule: .
- Transitivity: If and , then .
- Polynomial Rule: A degree- polynomial with is .
Answer:
Asymptotic notation expresses algorithm growth rates as . Big-O ( for ) satisfies constant-factor invariance, sum () rule, product rule, transitivity, and polynomial dominance.