Analyzing Algorithm Efficiency: Iterative vs. Recursive

What is Time Complexity?

Imagine you have two algorithms that solve the same problem. How do you decide which one is "better"? You could time them, but that depends on the computer's speed, the programming language, and the specific input you use. We need a more robust, machine-independent way to compare them.

Time complexity is a way to measure how the runtime of an algorithm scales as the size of the input grows. We're not interested in the exact number of seconds it takes, but rather in the rate of growth of the number of operations it performs.

Big O notation is the mathematical language we use to describe this growth rate, specifically focusing on the worst-case scenario as the input size (n) approaches infinity.

The Rules of Simplification

To find the Big O complexity, we first count the number of basic operations an algorithm performs in terms of its input size, n. This gives us a function, let's call it f(n). For example, an algorithm might perform f(n) = 2n + 1 operations.

However, Big O is about capturing the "big picture" of the growth. We simplify f(n) using a few key rules to find the dominant term that characterizes the algorithm's behavior for large n.

1. Drop Constants

As n gets very large, constant factors become insignificant. An algorithm that takes 2n steps and one that takes n steps both grow linearly. The 2 doesn't change the fundamental growth character.

• O(2n) becomes O(n)
• O(500) becomes O(1) (Constant time)

2. Drop Non-Dominant Terms

We only care about the term that grows the fastest. If you have a function like f(n) = n² + n + 100, as n becomes massive (e.g., a million), the n² term will be so much larger than n and 100 that the others become negligible.

• O(n² + n) becomes O(n²)
• O(n + log n) becomes O(n)
• O(2^n + n^3) becomes O(2^n)

Common Time Complexities

Algorithms generally fall into a few common complexity classes. It's essential to recognize them and understand their relative performance.

Here they are, from best (most efficient) to worst:

• O(1) - Constant: Runtime is independent of the input size. (e.g., accessing an array element by index).
• O(log n) - Logarithmic: Runtime grows logarithmically. Typically seen in algorithms that divide the problem in half at each step. Extremely efficient.
• O(n) - Linear: Runtime grows linearly with the input size. A common complexity for algorithms that iterate through an input once.
• O(n log n) - Linearithmic: A very common complexity for efficient sorting algorithms.
• O(n²) - Quadratic: Runtime grows with the square of the input size. Often involves nested loops over the same input. Becomes slow very quickly.
• O(2^n) - Exponential: Runtime doubles with each addition to the input. Often seen in recursive solutions that solve a problem of size n by making two separate recursive calls to problems of size n-1. Generally too slow for anything but very small inputs.
• O(n!) - Factorial: Runtime grows factorially. Extremely slow; only feasible for tiny n.

Analyzing Iterative Algorithms: Code Examples

Let's apply these rules to concrete Java code.

O(1) - Constant Time

The runtime doesn't depend on the input n.

// Given an array of numbers
int[] numbers = {10, 20, 30, 40, 50};

// This operation is O(1) because it takes the same amount of time
// whether the array has 5 elements or 5 million.
int firstElement = numbers[0];

// This is also O(1). The input 'n' does not affect the number of operations.
boolean isEven(int n) {
    return n % 2 == 0;
}

O(n) - Linear Time

A single loop that iterates from 0 to n.

// This function has a time complexity of O(n) because the loop
// runs 'n' times, where 'n' is the length of the array.
long sumArray(int[] arr) {
    long sum = 0; // O(1)
    for (int i = 0; i < arr.length; i++) { // Loop runs n times
        sum += arr[i]; // O(1) operation inside
    }
    return sum; // O(1)
}
// Total: O(1 + n*1 + 1) = O(n+2). After dropping constants, it's O(n).

What about two separate, non-nested loops?

void process(int[] arr) {
    // First loop
    for (int x : arr) {
        System.out.println(x);
    }
    // Second loop
    for (int y : arr) {
        System.out.println(y);
    }
}
// Complexity is O(n) + O(n) = O(2n), which simplifies to O(n).

O(n²) - Quadratic Time

A loop inside another loop. For each element in the outer loop, we iterate through the entire inner loop.

// Prints all pairs of elements in an array.
void printPairs(int[] arr) {
    // Outer loop runs n times.
    for (int i = 0; i < arr.length; i++) {
        // Inner loop also runs n times for each outer iteration.
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}
// Total operations are roughly n * n = n². So, O(n²).

A Note on Multiple Inputs

What if loops iterate over different arrays? We use different variables.

// arrayA has size 'a', arrayB has size 'b'
void printPairs(int[] arrayA, int[] arrayB) {
    for (int i = 0; i < arrayA.length; i++) { // Runs 'a' times
        for (int j = 0; j < arrayB.length; j++) { // Runs 'b' times
            System.out.println(arrayA[i] + ", " + arrayB[j]);
        }
    }
}
// Complexity is O(a * b). We cannot simplify to O(n²) because 'a' and 'b' could be very different.

void processData(int[] arr1, int[] arr2) {
    // Part 1
    for (int x : arr1) {
        System.out.println(x);
    }

    // Part 2
    for (int i = 0; i < arr1.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i] == arr2[j]) {
                System.out.println("Match found!");
            }
        }
    }
}

Analyzing Recursive Algorithms

Analyzing recursion involves thinking about the recursion tree. The time complexity is generally:

(Number of recursive calls) × (Work done in each call)

O(n) - Linear Recursion

Consider a recursive factorial function.

int factorial(int n) {
    if (n <= 1) {
        return 1; // O(1) base case
    }
    return n * factorial(n - 1); // O(1) work + recursive call
}

The function calls itself n times (factorial(n), factorial(n-1), ..., factorial(1)), and each call does a constant amount of work (a multiplication and a subtraction). The recursion tree is just a straight line of depth n.
Total complexity = n calls * O(1) work/call = O(n).

O(2^n) - Exponential Recursion

The classic example is the Fibonacci sequence.

int fibonacci(int n) {
    if (n <= 1) {
        return n; // O(1) base case
    }
    // TWO recursive calls are made in each step.
    return fibonacci(n - 1) + fibonacci(n - 2); 
}

Each call to fibonacci(n) generates two more calls, fibonacci(n-1) and fibonacci(n-2). This creates a branching recursion tree. The number of nodes in this tree grows exponentially, leading to a time complexity of roughly O(2^n). This is very inefficient.

O(log n) - Logarithmic Recursion

What if a recursive call halves the input size?

void function(int n) {
    if (n <= 1) {
        return; // Base case
    }
    // Do some O(1) work...
    function(n / 2); // Recurse on half the problem
}

If you start with n, the sequence of calls will be n, n/2, n/4, n/8, ..., 1. How many times can you divide n by 2 until you get to 1? The answer is log₂(n). Since each call does O(1) work, the total complexity is O(log n).

Conclusion

You've just been introduced to the single most important concept for analyzing algorithm efficiency. Understanding Big O notation is not just academic; it's a practical tool you will use daily to reason about your code's performance, especially in interviews.

Key Takeaways:

• Time complexity measures how an algorithm's runtime scales with input size n.
• Big O notation describes this scaling, focusing on the worst-case for large n.
• Simplification Rules: Always drop constants and non-dominant terms. O(2n² + 100n) is just O(n²).
• Iterative Analysis: Count the loops. A single loop is often O(n), nested loops are often O(n²), and loops that halve the search space are O(log n).
• Recursive Analysis: Think about the recursion tree. The complexity is the number of nodes in the tree. A single call that reduces n by a constant is O(n), while two calls can lead to O(2^n). A call that divides n leads to O(log n).

Preview of the next lesson:
Time is only half of the equation. An algorithm also consumes memory. In the next lesson, we will explore Space Complexity, learning how to analyze the amount of memory an algorithm uses, including the often-overlooked space taken up by the recursion stack.