PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q9

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Introduction

Question

Define big-O notation and Big- notation with their respective curves.

Solution

Big-O () Notation and Curve: iff there exist and such that for all . It defines an asymptotic upper bound.

  Time
   ^         c * g(n)
   |        /   ___--- f(n)
   |       / __/
   |      /_/
   +-----+------------> n
         n0

Big-Omega () Notation and Curve: iff there exist and such that for all . It defines an asymptotic lower bound.

  Time
   ^            f(n)
   |           /   ___--- c * g(n)
   |          / __/
   |         /_/
   +--------+---------> n
            n0
Answer:

Big-O ( for ) bounds growth from above (worst-case ceiling), whereas Big- ( for ) bounds growth from below (best-case floor).

All past exam questions for Data Structure and Algorithms