Team Teach Lesson - Big O Notation and Algorithmic Complexity

[SanPranav]

Big O Notation & Algorithmic Efficiency

Overview

Understanding how algorithms perform as input size grows is crucial. We use Big O notation to describe their efficiency. Big O notation helps us analyze:

• Time Complexity: How runtime increases with input size.
• Space Complexity: How much extra memory is needed.

---

What is Big O?

Big O notation expresses the worst-case scenario runtime of an algorithm. It provides an upper bound on how an algorithm behaves as the input size grows.

Common Big O Complexities

Complexity	Name	Example
O(1)	Constant	arr[0]
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Loop through an array
O(n log n)	Linearithmic	Merge Sort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci
O(n!)	Factorial	Permutations

---

Examples & Explanations

Constant Time – O(1)

def get_first_element(arr):
    return arr[0]

Takes the same amount of time, regardless of input size.

Even if arr has 1 or 1,000,000 elements, this function always runs in one step.

---

Linear Time – O(n)

def print_elements(arr):
    for item in arr:
        print(item)

Time grows proportionally with input size.

If arr has 5 elements, we run the loop 5 times. If it has 1,000 elements, we run it 1,000 times.

---

Quadratic Time – O(n²)

def print_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

As n grows, operations increase quadratically.

If arr has 10 elements, we perform 100 operations. If it has 100 elements, we perform 10,000 operations.

---

Logarithmic Time – O(log n)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Efficient for searching in sorted data.

Each step cuts the input size in half. Searching in 1,000,000 elements takes ~20 steps instead of 1,000,000.

---

Exponential Time – O(2ⁿ)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Very slow for large n.

For n = 10, this function does ~1000 calls. For n = 50, it does billions of calls.

---

Classwork Problems (Easy)

What is the time complexity of this function?

def sum_list(arr):
    total = 0
    for num in arr:
        total += num
    return total

Answer: O(n) – It loops through the list once.

---

What is the time complexity of accessing an element in an array?

def get_element(arr, index):
    return arr[index]

Answer: O(1) – Accessing an index takes constant time.

---

What is the complexity of this nested loop?

def nested_loops(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

Answer: O(n²) – The inner loop runs n times for each iteration of the outer loop.

---

Homework Problems (Harder)

What is the time complexity of this function?

def reverse_string(s):
    return s[::-1]

Answer: O(n) – It iterates through the string once to reverse it.

---

What is the complexity of this function that removes duplicates?

def remove_duplicates(arr):
    unique = set(arr)
    return list(unique)

Answer: O(n) – Creating a set and list both take linear time.

---

What is the complexity of this recursive function?

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

Answer: O(n) – The function calls itself n times.

---

Why Does Big O Matter?

• Efficient algorithms save time & resources
• Choosing the right algorithm can make or break an application
• Helps in scaling up programs for large data

---

Resources for Further Learning

📖 CS50: Big O Explanation 📖 Khan Academy: Algorithmic Efficiency 📖 Big O Cheatsheet 📖 VisuAlgo: Interactive Big O Demonstrations 📖 GeeksforGeeks: Big O Explained