Scribd
Upload
6 views1 page

Understanding Big O, Ω, and Θ Notations

The document explains algorithm notations: Big O, Big Ω, and Big Θ. Big O denotes the upper bound of an algorithm's running time, Big Ω indicates the lower bound, and Big Θ represents a tight bound encompassing both. Examples include linear search with time complexities of O(n), Ω(1), and Θ(n) respectively.

Uploaded by

mnithinshetty841
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Understanding Big O, Ω, and Θ Notations

The document explains algorithm notations: Big O, Big Ω, and Big Θ. Big O denotes the upper bound of an algorithm's running time, Big Ω indicates the lower bound, and Big Θ represents a tight bound encompassing both. Examples include linear search with time complexities of O(n), Ω(1), and Θ(n) respectively.

Uploaded by

mnithinshetty841
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Notations - Big O, Big Ω, Big Θ

16. Big O Notation (Upper Bound)


• Definition: Big O notation describes the upper bound of an algorithm’s running time. It gives the
worst-case growth rate.
• Meaning: It tells us how fast the time (or space) will grow at most, as input size increases.
• Mathematical Form: f(n) = O(g(n)) if there exist constants c > 0 and n■ such that f(n) ≤ c·g(n) for
all n ≥ n■.
• Example: Linear search in an array of size n takes at most n comparisons → Time complexity =
O(n).

17. Big Omega Notation (Lower Bound)


• Definition: Big Ω notation describes the lower bound of an algorithm’s running time. It gives the
best-case growth rate.
• Meaning: It tells us the minimum time an algorithm will take as input size increases.
• Mathematical Form: f(n) = Ω(g(n)) if there exist constants c > 0 and n■ such that f(n) ≥ c·g(n) for
all n ≥ n■.
• Example: Linear search → if the element is at the first position, only 1 comparison is needed →
Time complexity = Ω(1).

18. Big Theta Notation (Tight Bound)


• Definition: Big Θ notation describes the tight bound (both upper and lower) of an algorithm’s
running time.
• Meaning: It gives the average/precise growth rate, when the algorithm takes between best and
worst cases in a proportional manner.
• Mathematical Form: f(n) = Θ(g(n)) if there exist constants c■, c■ > 0 and n■ such that c■·g(n) ≤
f(n) ≤ c■·g(n) for all n ≥ n■.
• Example: Linear search requires between 1 and n comparisons → Time complexity = Θ(n).

Notation Meaning Bound Type Case Represented Example (Linear Search)


Big O (O) Upper bound of growth rate Worst-case Maximum time takenO(n) → at most n comparisons
Big Ω (Ω) Lower bound of growth rate Best-case Ω(1) → element found at first position
Minimum time taken
Θ (Θ)
BigTight bound of growth rate (both upper
Average/Exact
& lower) Θ(n) → between 1 and n comparisons
case Typical growth rate

You might also like