Introduction to DSA, Big-O, Big-Omega & Big-Theta Notations0%
Time Complexity Calculation Rules & Common Runtime Patterns

Introduction to DSA, Big-O, Big-Omega & Big-Theta Notations

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Introduction to DSA, Big-O, Big-Omega & Big-Theta Notations

Data Structures and Algorithms (DSA) represent the foundational engineering science of software development. A Data Structure is a specialized format for organizing, storing, and retrieving data in computer memory, while an Algorithm is an unambiguous step-by-step computational procedure that transforms input into desired output.

1. Real-World Analogy: The City Library Index

Imagine a city library with 500,000 books dumped into a single giant pile on the floor. Finding "Harry Potter" would require inspecting every single book one by one from top to bottom. If examining each book takes 1 second, it could take up to 5.7 days to find a book!

Now imagine the books are organized on alphabetized bookshelves with a Dewey Decimal index catalog. You walk straight to Section H, Row 4, and retrieve the book in under 20 seconds.

  • The Bookshelf & Catalog system is the Data Structure.
  • The Binary Search lookup technique you used to reach the H shelf is the Algorithm.

2. Asymptotic Notations: Measuring Efficiency

Computers vary wildly in hardware specifications. An algorithm running on a 64-core supercomputer will execute faster in clock time than on a 10-year-old smartphone. Therefore, computer scientists do not measure algorithm efficiency in seconds; instead, we analyze how the number of computational operations grows as the input size ($n$) scales towards infinity.

Big-O Complexity CurvesClick to Zoom
Big-O Complexity Curves

The Three Pillars of Asymptotic Notation

  1. 1
    Big-O ($O$) — Worst-Case Upper Bound: Represents the absolute maximum number of operations an algorithm will ever take. In technical interviews and production SLAs, Big-O is what engineers care about most because it guarantees performance limits.
  2. 2
    Big-$\Omega$ ($\Omega$) — Best-Case Lower Bound: The minimum number of steps required under optimal input conditions (e.g., finding the target at index 0 of an array on the first guess).
  3. 3
    Big-$\Theta$ ($\Theta$) — Tight Bound: Occurs when the best-case and worst-case growth rates match asymptotically.

3. Common Time Complexity Classes

Big-O ClassNameOperations for $n = 10^6$Typical Examples
$O(1)$Constant Time$\approx 1$ stepArray index lookup, Hash Map get/put, Stack push
$O(\log n)$Logarithmic Time$\approx 20$ stepsBinary Search, Balanced BST search
$O(n)$Linear Time$\approx 10^6$ stepsLinear scan, finding array maximum, Two-pointer pass
$O(n \log n)$Linearithmic$\approx 2 \times 10^7$ stepsMerge Sort, Quick Sort (average), Heap Sort
$O(n^2)$Quadratic Time$\approx 10^{12}$ stepsNested loops, Bubble Sort, pairwise combinations
$O(2^n)$Exponential Time$> 10^{300,000}$ stepsRecursive Fibonacci, generating all power sets

4. Code Comparison: $O(1)$ vs $O(n)$ vs $O(n^2)$

Python 3 Implementation:

Python
# 1. Constant Time O(1): Instantaneous regardless of array size
def get_first_element(arr: list[int]) -> int:
return arr[0] if arr else -1
 
# 2. Linear Time O(n): Single loop traversing n items
def calculate_sum(arr: list[int]) -> int:
total = 0
for num in arr:
total += num
return total
 
# 3. Quadratic Time O(n^2): Nested loops checking all pairs
def has_duplicate_pairs(arr: list[int]) -> bool:
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False

Modern JavaScript / TypeScript Implementation:

TypeScript
// 1. Constant Time O(1)
export function getFirstElement<T>(arr: T[]): T | undefined {
return arr[0];
}
 
// 2. Linear Time O(n)
export function calculateSum(arr: number[]): number {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}
 
// 3. Quadratic Time O(n^2)
export function hasDuplicatePairs(arr: number[]): boolean {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}

5. Step-by-Step Dry Run: Input Scaling Test

Input Size ($n$)$O(1)$ Steps$O(\log_2 n)$ Steps$O(n)$ Steps$O(n^2)$ Steps
1013.310100
10016.610010,000
1,0001101,0001,000,000
1,000,0001201,000,000$10^{12}$ (Crash/Timeout)
Interactive Quiz

Multiple Choice Questions

Question 1
What does Big-O notation ($O$) describe in algorithm analysis?
Question 2
If an algorithm takes 20 steps to process 1,000,000 items and approximately 30 steps to process 1,000,000,000 items, what is its time complexity?
Question 3
Which notation represents the best-case (lower bound) performance of an algorithm?
Question 4
What is the time complexity of looking up a value in an array given its numeric index (e.g., arr[42])?
Question 5
Why do competitive programming platforms and technical interviewers fail solutions with $O(n^2)$ complexity when $n = 10^5$?
Next Lesson

Time Complexity Calculation Rules & Common Runtime Patterns

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
NoneTime Complexity Calculation Rules & Common Runtime Patterns

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

Next
PrevNext