PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q8(a)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Introduction

Question

Define Big 'O' notation and describe the rules to determine the order of common functions. Compare linear, quadratic, logarithmic, linear logarithmic order functions.

Solution

Big 'O' Notation & Rules for Determining Order: iff there exist such that for all . Rules for Order Determination:

  1. Drop Multiplicative Constants: .
  2. Keep Only Highest-Order Term (Sum Rule): .
  3. Nested Loops Multiply (Product Rule): A loop of inside gives .
  4. Logarithm Base Invariance: for any constant bases .

Comparison of Common Growth Orders (Slowest to Fastest Growth):

OrderNameGrowth at Typical Algorithm Example
LogarithmicBinary search, AVL lookup
LinearSequential search, array traversal
Linear-LogarithmicMerge sort, Heap sort, Quick sort (avg)
QuadraticBubble, Insertion, Selection sort
Answer:

Big-O bounds worst-case growth from above using constant-dropping, dominant-term sum, and loop-product rules. Growth order ranks: .

All past exam questions for Data Structure and Algorithms