Introduction to Algorithms

An algorithm is a finite, ordered sequence of well-defined instructions for solving a problem. Every program you write is a composition of algorithms.

Why Complexity Matters

When choosing an algorithm, we care about two resources:

• Time complexity — how does runtime grow as input size n grows?
• Space complexity — how much extra memory is required?

We describe this growth with Big O notation, which captures the worst-case upper bound.

Common Complexities (best → worst)

Notation	Name	Example
O(1)	Constant	Array index lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear scan
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Bubble sort
O(2ⁿ)	Exponential	Naïve Fibonacci

Key Insight: Drop Constants and Lower Terms

Big O strips away constants and lower-order terms because they become irrelevant at scale:

• 3n + 100 → O(n)
• n² + n + 5 → O(n²)
• 5 * log(n) → O(log n)

Practice Prompt

Given this function, what is its time complexity?

def find_pair_sum(nums, target):
    seen = set()
    for n in nums:
        if target - n in seen:
            return True
        seen.add(n)
    return False

Answer: O(n) time, O(n) space — single pass with a hash set.

Next Up

With complexity intuition in hand, you're ready to compare sorting algorithms and understand why merge sort beats bubble sort on large inputs.