Big O and Algorithm Efficiency

None
Apr 11, 2025 • 2 min read

Collaboration

Big O Notation

Introduction

Big O notation is used to describe the efficiency of algorithms in terms of time complexity and space complexity. It helps us understand how an algorithm scales as the input size increases.

Common Big O Complexities

Notation	Complexity Class	Description
O(1)	Constant Time	Execution time is the same regardless of input size.
O(log n)	Logarithmic Time	Execution time increases logarithmically with input size.
O(n)	Linear Time	Execution time grows proportionally to input size.
O(n log n)	Linearithmic Time	Common in efficient sorting algorithms like Merge Sort and Quick Sort.
O(n²)	Quadratic Time	Execution time grows quadratically with input size.
O(2ⁿ)	Exponential Time	Execution time doubles with each additional element.
O(n!)	Factorial Time	Execution time grows factorially — very inefficient for large inputs.

Examples

O(1) - Constant Time

arr = [1, 2, 3, 4, 5]
print(arr[2])  # Accessing an element by index takes constant time.

O(n) - Linear Time

arr = [1, 2, 3, 4, 5]
for num in arr:
    print(num)  # Time grows with the array size.

Popcorn Hack #1

Given:

arr = [1, 2, 3, 4, 5]

Print the third item using constant time:

print(arr[2])  # O(1)

Print all the items using linear time:

for num in arr:
    print(num)  # O(n)

1
2
3

O(n²) - Quadratic Time

arr = [1, 2, 3]
for i in arr:
    for j in arr:
        print(i, j)  # Nested loop: O(n²)

Popcorn Hack #2

Task: Print all unique pairs from [1, 2, 3]

def print_unique_pairs(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            print(f"({arr[i]}, {arr[j]})")

arr = [1, 2, 3]
print_unique_pairs(arr)

(1, 2)
(1, 3)
(2, 3)

Time Complexity:
O(n²) — because for each element, you’re iterating through the rest of the list using a nested loop.

O(log n) - Logarithmic Time

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

Popcorn Hack #3

Q1: Which of these is inefficient for large inputs?

a) Linear Time
b) Factorial Time ✅
c) Constant Time
d) Linearithmic Time

Q2: Which of these can be represented by a nested loop?

a) Logarithmic Time
b) Linearithmic Time
c) Quadratic Time ✅
d) Linear Time

Homework Hack

Function that acts based on complexity:

def perform_operation(arr, complexity):
    if complexity == "constant":
        return arr[0]
    elif complexity == "linear":
        for item in arr:
            print(item)
    elif complexity == "quadratic":
        for i in arr:
            for j in arr:
                print(i, j)
    else:
        return "Unsupported complexity"

# Example usage:
arr = [5, 10, 15, 20, 25]
perform_operation(arr, "linear")