Sitemap
Girish Rane

Girish Rane

Software Engineer

Member-only story

2. Complexity Notation

3 min readNov 13, 2026

Free user: Click here

For the 1st post, please click here

Press enter or click to view image in full size

Understanding algorithmic complexity is fundamental to algorithmic thinking. Complexity notations provide a formal framework to measure, compare, and reason about algorithm performance in terms of time and space. In C++, these theoretical concepts can be experimentally validated using microbenchmarks, bridging the gap between theory and practice

Introduction to Complexity Notation

Algorithmic complexity describes how an algorithm’s resource usage grows with input size. The most common measures are:

Big-O Notation (O):

Represents the upper bound on runtime or space. • Provides a worst-case guarantee: the algorithm will not exceed this growth rate. • Example: Insertion sort has O(n²) worst-case complexity.

Big-Theta Notation (Θ):

  • Represents the tight bound, where the growth rate is both an upper and lower bound.
  • Provides an exact asymptotic behavior.
  • Example: Merge sort has Θ(n log n) complexity in both average and worst cases.

Big-Omega Notation (Ω):

  • Represents the lower bound, i.e., the minimum amount of work an algorithm will do.

--

--