PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q10

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Introduction

Question

Define Big-Oh and Theta notation with suitable example.

Solution

Big-Oh Notation () — Asymptotic Upper Bound: Mathematical Definition: Let and be functions mapping positive integers to non-negative real numbers. We say:

if and only if there exist positive constants and such that:

Interpretation: Big-Oh provides an asymptotic upper bound on the growth rate of . It guarantees that as the input size grows arbitrarily large, the running time of the algorithm will never exceed (characterizing worst-case performance).

Example for Big-Oh Notation: Let . Prove that .

For all :

Thus, we have:

By choosing constant multiplier and threshold , the formal definition is strictly satisfied for all . Hence:

Theta Notation () — Asymptotic Tight Bound: Mathematical Definition: Let and be non-negative functions. We say:

if and only if there exist positive constants , , and an integer such that:

Interpretation: Theta notation sandwiches from both above and below within constant factor multiples of . This means grows at the identical asymptotic rate as ( and simultaneously).

Example for Theta Notation: Using the same function . Prove that .

  1. Lower Bound (): For all :
  1. Upper Bound (): For all :

Combining both inequalities for all :

With , , and , the definition of holds. Therefore:

Answer:

All past exam questions for Data Structure and Algorithms