A much-improved Fibonacci approach

 In the last article, we looked in depth at the enormous cost of even fib(7) by drawing out the tree of calls for it and realizing that going even to fib(8) would be much more expensive. The traditional recursive way, we concluded, was beautiful and simple, but terribly inefficient due to its exponential runtime.

Of course, almost anything is better than an exponential runtime, so we’ll take any improvement we can get.  But here’s the good news: I claim (and will soon prove) that I have a method that takes O(2^n) down to O(n). Those are enormous savings: in the first case, if n is 10, you do 1024 operations, whereas in the second case, with the same n, you only do 10—saving >=99% of the work from the exponential version, getting the answer that much more quickly and efficiently.

Here's how we can do it:

• Set up an array
• Use the array to remember values you’ve already calculated
• Look them up, instead of recalculating them
• Keep adding values as you calculate new ones

For comparison’s sake, let’s go calculate fib(7). For this, we need an array storing 8 integers, so we can index them from 0 to 7.

Initially, of course, the array looks like

Index	0	1	2	3	4	5	6	7
Value	0	0	0	0	0	0	0	0

But we can start by populating the values of the base cases, given in the recursive formula, namely, that fib(0)—or, here, in this context, fib[0] with square brackets because we’re accessing an index of an array, not calling a function—is 1, and so is fib[1].

Index	0	1	2	3	4	5	6	7
Value	1	1	0	0	0	0	0	0

 

Now, from fib[2] onward, let’s simply loop through the array and do one of two things:

• Use an existing value
• Update a 0 into a real value, where necessary

fib[2] is not a base case, but we know the rule is to add the previous two, so this is as simple as fib[2] = fib[0] + fib[1];

Index	0	1	2	3	4	5	6	7
Value	1	1	2	0	0	0	0	0

Now, we have fib[2] saved somewhere, and we’ll save ourselves a lot of time by not throwing that result away.

We do the same for fib[3], which is fib[2] + fib[1]. fib[1] was a base case, so we hard-coded that earlier, and we just calculated and saved fib[2], so we can use it

Index	0	1	2	3	4	5	6	7
Value	1	1	2	3	0	0	0	0

 
Likewise, to get fib[4] by looking up (rather than recalculating) fib[2] and fib[3]:

Index	0	1	2	3	4	5	6	7
Value	1	1	2	3	5	0	0	0

 
Likewise, to get fib[5] by looking up (rather than recalculating) fib[3] and fib[4]:

Index	0	1	2	3	4	5	6	7
Value	1	1	2	3	5	8	0	0

 

Likewise, to get fib[6] by looking up (rather than recalculating) fib[4] and fib[5]:

Index	0	1	2	3	4	5	6	7
Value	1	1	2	3	5	8	13	0

 

Likewise, to get fib[7]—our final answer— by looking up (rather than recalculating) fib[5] and fib[6]:

Index	0	1	2	3	4	5	6	7
Value	1	1	2	3	5	8	13	21

This technique of storing a value and using it later is called memoizing (for as much trouble as my word processor gives me, there is no “r” as in “memoRizing”—it’s “memoizing” as in “writing a memo”) and is key to a pattern of programming called dynamic programming, which we’ll start covering explicitly soon.

This way, you still have the relationship that f(n) = f(n-1) + f(n-2), but, thanks to the fact that you’re storing these values somewhere, you don’t need to waste any time redoing past calculations. 


Using a HashMap, we can write this much-improved solution like this:

import java.util.HashMap;

import java.util.Map;

public class FibonacciMemoization {

    // Cache to store already computed Fibonacci values

    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fibonacci(int n) {

        // Base cases

        if (n == 0) return 0;

        if (n == 1) return 1;

        // Check if already computed

        if (memo.containsKey(n)) {

            return memo.get(n);

        }

        // Compute, store, and return

        long result = fibonacci(n - 1) + fibonacci(n - 2);

        memo.put(n, result);

        return result;

    }

}

Issues with a Naive Fibonacci

 Let’s look in detail at a naïve—that is, simple and elegant, but computationally expensive (you’ll get O(2^n)) way to implement Fibonacci. This, perhaps, was the way you learned how to implement it when you first came across the idea of recursive programming.

Fibonacci is defined very simply:

• Fib(0) is 1
• Fib(1) is 1
• Fib(n) is the sum of Fib(n-1) and Fib(n-2) for all other n >=2

This last step is what makes it recursive—and, unfortunately, what makes the elegant recursive solution. Let’s look at why.

The following is as literal (and correct) a translation of the 3 bullet points above as possible:

public static int fibonacci(int n) {

    if (n == 0 || n == 1) {

        return n;

    }

    return fibonacci(n - 1) + fibonacci(n - 2);

}

There’s a problem with this code; even if not in theory, in practice: It repeats a lot  of work unnecessarily.

Suppose we need fib(10). Then we need

·       Fib(9)

o   For which we need fib(8)

§  For which we need fib(7)

·       For which we need fib(6)

·       And fib(5)

§  And fib(6)

·       For which we need fib(5)

·       And fib(4)

o   and fib(7)

·       Fib(8)

o   for which we need fib(7)

o   and fib(6)

 

The tree of calls isn’t even complete—this is why Fibonacci takes so long, O(2^n)—and look at how many times I’m repeating that I need royal blue, or turquoise, or any other color. And realize that, if, for example, I need fib(100), I need to do that whole tree’s worth of calculation before I can find the answer, even if fib(100) is just an intermediary goal.

Of course, using fib(100) is quite an extreme example, but it does its job: show just how much work you repeat due to the exponential nature of the problem.

Let’s actually look at a tree showing the sequence of calls for fib(7) to see just how much work is repeated, on our way, in the next article, to a better (if less obvious and elegant) way to calculate Fibonacci that saves orders of magnitude of time and memory:

 

Fib(7), by definition, requires fib(6) and fib(5). But here’s the problem: the traditional approach is to calculate fib(6) and throw away the intermediate results, including an answer we need anyway before calculating fib(5), which was already part of fib(6) but which we foolishly threw away.

We get the O(2^n) complexity from the fact that the naïve formula splits us up into 2 scenarios and has us calculate each one independently, and we see that given the branching of the tree. 2^n grows very, very quickly, so while this approach always remains correct, very quickly, it degrades in efficiency, so the method we’ll propose in the next article takes over as the best way to approach this problem.                

More Complexity Analysis

 The first step in learning how to categorize—and then build—efficient code is learning the basic patterns we covered in the first article on complexity:

• a number of steps that doesn’t change with respect to the input size is constant complexity—like accessing some spot in memory
• a number of steps that’s proportional to the log of the input size is logarithmic complexity—like binary search
• a number of steps that’s proportional to the input size is linear complexity—like linear search (this is why it has that name)
• a number of steps that’s proportional to some power of the input size is quadratic complexity—like anything with a loop inside a loop inside a loop inside a loop … 
• etc. 

Each complexity class has some recognizable patterns, that, at a glance, tell you the complexity of some code. 

This, for example, has quadratic complexity:

public boolean findDuplicates(int[] inputData) {

    for (int i = 0; i < inputData.length; i++) {

        for (int j = 0; j < inputData.length; j++) {

            if (inputData[i] == inputData[j] && i != j) {

                return true;

            }

        }

    }

    return false;

}

For every i, for every j (in other words i*j times), we do a thing. 

Now, let’s look at this code:

public class NLogNLoopDemo {

    public static void main(String[] args) {

        int n = 16; // You can change this value to see how it scales

        int count = 0;

        for (int i = 0; i < n; i++) {           // O(n)

            for (int j = 1; j < n; j = j * 2) { // O(log n)

                System.out.println("i = " + i + ", j = " + j);

                count++;

            }

        }

        System.out.println("Total iterations: " + count);

    }

}

For every i, for a small subset of the j’s (those that are double as far away as the previous j—which does not mean “half the j’s”), we do a thing. This setup is nlogn. 

What I want to talk about now assumes you’re comfortable looking at code and seeing these patterns—so you know MergeSort is in nlogn, or looping through an array once is n—but how we take these classifications and make decisions based on them. 

Recall the case of BubbleSort. Because of how the bubbling mechanism works, the best scenario is when the array is already sorted—and then the algorithm just does one pass in linear time to check that that’s the case. 

But the worst case is that the array is already sorted, but in the opposite order. In that case, the algorithm does n-1 swaps to get the first number in place, then n-2, then n-3, then n-4…; and the whole sum of these numbers is proportional to n^2, so in the worst case, BubbleSort is n^2. 

On average, we’ll fall somewhere in the middle. With randomized numbers, some will be sorted, and some won’t be sorted. The average of n and n^2 is (n+n^2)/2, which we actually consider to be n^2. This is because of two reasons already alluded to in our first discussion

• n^2 dominates n, so taking a shortcut and calling “n^2+n”, as things go to their limits, is perfectly acceptable 
• We ignore constants. 2n^2 looks the same (except for a stretch) compared to n^2; we only say that functions are “different” if they really are, like n^2 and n!. 

In computer science, we often do three kinds of analysis on an algorithm (for time and/or space, so, I guess, six types):

• If everything is as easy as possible for the algorithm, what’s the best-case scenario for its performance?
• If everything is how we expect it to be on average, what’s the average-case scenario for its performance?
• If everything is as hard as possible for the algorithm, what’s the worst-case scenario for its performance?

Most of the time, however, when designing software, you care much more about the worst-cases than the best. 

For each of these, we have 3 possible classes they could fit into: Omega (Ω), Theta (Θ), and Big-O (denoted with the familiar Latin-alphabet “O”, as in “the letter before P,” not a 0):

If an algorithm’s cost function is Big-Omega of a certain class of functions, then it means there is some constant C, such that for C times the class is always less than the cost function. That is, the cost function always performs worse than the constant-times-class, and constant-times-class is therefore a lower bound.  

If an algorithm’s cost function is Big-Omega of a certain class of functions, then it means there is some constant C, such that for C times the class is always less than the cost function. That is, the cost function always performs worse than the constant-times-class, and constant-times-class is therefore a lower bound. You will not do any better than this lower bound.   

If an algorithm’s cost function is Big-O of a certain class of functions, then it means there is some constant C, such that for C times the class is always greater than the cost function. That is, the cost function always performs better than the constant-times-class, and constant-times-class is therefore an upper bound.  You will not do any worse than this lower bound. 

If an algorithm is both Big-O and Big-Omega of some cost function class, then you have enough evidence to state that it’s Big-Theta of that class.

 We need to draw an important distinction between best/worst/average and Omega/Theta/O: For each of the cases (best/worst/average), you can perform Omega/Theta/O analysis. Omega is not the exclusive domain of the best case (which can have its own big-O and potentially big-Theta), and O is not the exclusive domain of the worst case (which can have its own big-Omega and potentially big-Theta). It is perfectly fine to say that “the worst case scenario of [some code] is ‘big-Omega of n^2’” or that “the average case is ‘big-O of nlogn’”

File I/O

We have seen Scanner used to quickly gather one line, for example, to turn "Hello World" into a personalized "Hello, Andre" or something similar. But there are better ways to handle reading and writing much larger amounts of text: whole files.

BufferedReader and BufferedWriter are commonly used in Java to efficiently read from and write to text files. BufferedReader reads text from a file line by line, which is useful for processing large files without loading the entire contents into memory at once. For example, to read every line from a file and print it to the console, you can use:

BufferedReader reader = new BufferedReader(new FileReader("input.txt"));

String line;

while ((line = reader.readLine()) != null) {

    System.out.println(line);

}

reader.close();

This code opens "input.txt", reads each line until the end of the file, prints each line, and then closes the reader to free resources.

BufferedWriter is used for writing text to files efficiently. It buffers the output, so writing many small pieces of data is faster. For example, to write a couple of lines to a file:

BufferedWriter writer = new BufferedWriter(new FileWriter("output.txt"));

writer.write("This is the first line.");

writer.newLine();

writer.write("This is the second line.");

writer.close();

This code creates or overwrites "output.txt", writes two lines, and closes the writer when done.

If you want to copy the contents of one file to another, you can combine both classes:

BufferedReader reader = new BufferedReader(new FileReader("input.txt"));

BufferedWriter writer = new BufferedWriter(new FileWriter("output.txt"));

String line;

while ((line = reader.readLine()) != null) {

    writer.write(line);

    writer.newLine();

}

reader.close();

writer.close();

This reads each line from "input.txt" and writes it to "output.txt", preserving the line structure.

Always remember to close both the reader and writer after use, as this ensures all data is properly written and resources are released. BufferedReader and BufferedWriter are the preferred way to handle text files in Java when you need efficiency and simplicity.