Space Complexity for Java Dev : Beginners

Scenario:

Jr: My prime number finder uses a boolean array to mark non-prime numbers. How can we improve the memory usage?

Sr: The boolean array approach uses O(n) space. However, the Sieve of Eratosthenes algorithm provides an optimized way with the same space complexity but improved memory utilization.

Jr: How does Sieve of Eratosthenes work mathematically?

Sr: The Sieve algorithm works on the principle of eliminating multiples of prime numbers. It starts by marking all numbers as potential primes and iterates up to the square root of n. For each prime number found, it marks all of its multiples as non-prime. This method takes O(n log log n) time complexity and O(n) space complexity.

public void sieveOfEratosthenes(int n) {
    boolean[] primes = new boolean[n + 1];
    Arrays.fill(primes, true);

    for (int i = 2; i * i <= n; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (primes[i]) {
            System.out.print(i + " ");
        }
    }
}

Jr: So, it's a more optimized way to mark non-primes without using extra space for a separate array?

Sr: Precisely! This algorithm is more efficient for larger ranges as it sieves out non-prime numbers mathematically.

Jr: Can we explore another example with Fibonacci?

Sr: Certainly! The recursive Fibonacci approach uses O(n) space due to the recursive function call stack. However, an iterative approach like this:

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int prev = 0, current = 1;
    for (int i = 2; i <= n; i++) {
        int temp = current;
        current = current + prev;
        prev = temp;
    }
    return current;
}

Sr: Mathematically, this iterative version uses only O(1) space as it avoids creating those additional function calls. Understanding these complexities helps us select the most efficient approach for different scenarios and larger computations.