PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q7(a)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Introduction

Question

Define Big 'O' notation. Compare linear logarithmic, linear and quadratic order function.

Solution

Big 'O' Notation & Order Comparison: iff there exist such that for all .

Comparing growth rates as increases:

OrderTypical Example
Linear Linear search, array sum
Linear-Logarithmic Merge sort, Heap sort
Quadratic Bubble, Selection, Insertion sort
Answer:

Big-O gives an asymptotic upper bound. Growth speeds satisfy , with quadratic growing dramatically faster than linear and linear-logarithmic at large .

All past exam questions for Data Structure and Algorithms