PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q7

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Introduction

Question

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:

  1. Constant Factor Rule: For any constant , .
  2. Sum Rule (Dominant Term): If and , then .
  3. Product Rule: .
  4. Transitivity: If and , then .
  5. 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.

All past exam questions for Data Structure and Algorithms