PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q3(b)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Introduction

Question

Define Omega ana Theta notation with suitable example.

Solution

Big-Omega () Notation (Asymptotic Lower Bound): A function is in if there exist positive constants and such that:

It describes the minimum growth rate (best/lower bound) of an algorithm's running time.

Big-Theta () Notation (Asymptotic Tight Bound): A function is in if there exist positive constants and such that:

Equivalently, if and only if and .

Thus with , , , we have .

Answer:

All past exam questions for Data Structure and Algorithms