PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q9

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Introduction

Question

Describe the importance of growth function in algorithm. Discuss about theta function, Big-Oh function and Omega function.

Solution

Importance of Growth Function: A growth function models how an algorithm's execution time or memory scales with input size . It matters because:

  1. It reveals which algorithm remains practical as grows large (e.g., vs. for ).
  2. It ignores machine-specific constants so algorithms can be compared independently of CPU speed or compiler.
  3. It guides selection of data structures (e.g., hash table vs. array) before coding.

Big-Oh (), Big-Omega (), and Theta () Functions:

Answer:

A growth function predicts scalability with input size independent of hardware. gives an asymptotic upper bound, gives an asymptotic lower bound, and gives a tight two-sided bound.

All past exam questions for Data Structure and Algorithms