A Common-Sense Guide to Data Structures and Algorithms

We can never say with definitiveness that any operation takes, say, five seconds. While the same operation may take five seconds on a particular computer, it may take longer on an older piece of hardware, or much faster on the supercomputers of tomorrow. Measuring the speed of an operation in terms of time is flaky, since it will always change depending on the hardware that it is run on. However, we can measure the speed of an operation in terms of how many steps it takes. If Operation A takes five steps, and Operation B takes 500 steps, we can assume that Operation A will always be faster than Operation B on all pieces of hardware. Measuring the number of steps is therefore the key to analyzing the speed of an operation. Measuring the speed of an operation is also known as measuring its time complexity. Throughout this book, we’ll use the terms speed, time complexity, efficiency, and performance interchangeably. They all refer to the number of steps that a given operation takes.

Reading from an array is, therefore, a very efficient operation, since it takes just one step. An operation with just one step is naturally the fastest type of operation. One of the reasons that the array is such a powerful data structure is that we can look up the value at any index with such speed.

but this basic search operation—in which the computer checks each cell one at a time—is known as linear search.

So it turns out that for an array of five cells, the maximum number of steps that linear search would take is five. For an array of 500 cells, the maximum number of steps that linear search would take is 500. Another way of saying this is that for N cells in an array, linear search will take a maximum of N steps. In this context, N is just a variable that can be replaced by any number.

insertions for arrays are more efficient than insertions for sets.

Although the word algorithm sounds like something complex, it really isn’t. An algorithm is simply a particular process for solving a problem.

The major advantage of an ordered array over a standard array is that we have the option of performing a binary search rather than a linear search. Binary search is impossible with a standard array because the values can be in any order.

With an array containing one hundred values, here are the maximum numbers of steps it would take for each type of search: • Linear search: one hundred steps • Binary search: seven steps

The pattern that emerges is that for every time we double the number of items in the ordered array, the number of steps needed for binary search increases by just one. This pattern is unusually efficient: for every time we double the data, the binary search algorithm adds a maximum of just one more step. Contrast this with linear search. If you had three items, you’d need up to three steps. For seven elements, you’d need a maximum of seven steps. For one hundred, you’d need up to one hundred steps. With linear search, there are as many steps as there are items. For linear search, every time we double the number of elements in the array, we double the number of steps we need to find something. For binary search, every time we double the number of elements in the array, we only need to add one more step.

It’s also important to realize that there usually isn’t a single data structure or algorithm that is perfect for every situation. For example, just because ordered arrays allow for binary search doesn’t mean you should always use ordered arrays. In situations where you don’t anticipate searching the data much, but only adding data, standard arrays may be a better choice because their insertion is faster.

In order to help ease communication regarding time complexity, computer scientists have borrowed a concept from the world of mathematics to describe a concise and consistent language around the efficiency of data structures and algorithms. Known as Big O Notation, this formalized expression around these concepts allows us to easily categorize the efficiency of a given algorithm and convey it to others. Once you understand Big O Notation, you’ll have the tools to analyze every algorithm going forward in a consistent and concise way—and it’s the way that the pros use.

we discovered that reading from an array takes just one step, no matter how large the array is. The way to express this in Big O Notation is: O( 1) Many pronounce this verbally as “Big Oh of 1.” Others call it “Order of 1.” My personal preference is “Oh of 1.” While there is no standardized way to pronounce Big O Notation, there is only one way to write it. O( 1) simply means that the algorithm takes the same number of steps no matter how much data there is. In this case, reading from an array always takes just one step no matter how much data the array contains. On an old computer, that step may have taken twenty minutes, and on today’s hardware it may take just a nanosecond. But in both cases, the algorithm takes just a single step. Other operations that fall under the category of O( 1) are the insertion and deletion of a value at the end of an array. As we’ve seen, each of these operations takes just one step for arrays of any size, so we’d describe their efficiency as O( 1). Let’s examine how Big O Notation would describe the efficiency of linear search. Recall that linear search is the process of searching an array for a particular value by checking each cell, one at a time. In a worst-case scenario, linear search will take as many steps as there are elements in the array. As we’ve previously phrased it: for N elements in the array, linear search can take up to a maximum of N steps. The appropriate way to express this in Big O Notation is: O( N) I pronounce this as “Oh of N.” O( N) is the “Big O” way of saying that for N elements inside an array, the algorithm would take N steps to complete. It’s that simple.

Big O answers the following question: how does the number of steps change as the data increases?

You’ll see that O( N) makes a perfect diagonal line. This is because for every additional piece of data, the algorithm takes one additional step. Accordingly, the more data, the more steps the algorithm will take. For the record, O( N) is also known as linear time. Contrast this with O( 1), which is a perfect horizontal line, since the number of steps in the algorithm remains constant no matter how much data there is. Because of this, O( 1) is also referred to as constant time.

an algorithm can be described as O( 1) even if it takes more than one step. Let’s say that a particular algorithm always takes three steps, rather than one—but it always takes these three steps no matter how much data there is.

O( 1) is the way to describe any algorithm that doesn’t change its number of steps even when the data increases.

O( log N) is the Big O way of describing an algorithm that increases one step each time the data is doubled. As we learned in the previous chapter, binary search does just that.

Of the three types of algorithms we’ve learned about so far, they can be sorted from most efficient to least efficient as follows: O( 1) O( log N) O( N)

Another way of explaining log2 8 is: if we kept dividing 8 by 2 until we ended up with 1, how many 2s would we have in our equation? 8 / 2 / 2 / 2 = 1 In other words, how many times do we need to divide 8 by 2 until we end up with 1? In this example, it takes us 3 times. Therefore, log2 8 = 3. Similarly, we could explain log2 64 as: how many times do we need to halve 64 until we end up with 1? 64 / 2 / 2 / 2 / 2 / 2 / 2 = 1 Since there are 6 2s, log2 64 = 6.

Whenever we say O( log N), it’s actually shorthand for saying O( log2 N). We’re just omitting that small 2 for convenience.

With Big O, you have the opportunity to compare your algorithm to general algorithms out there in the world, and you can say to yourself, “Is this a fast or slow algorithm as far as algorithms generally go?”

Bubble Sort: in each passthrough, the highest unsorted value “bubbles” up to its correct position.

there are times where two competing algorithms may be described in exactly the same way using Big O Notation, yet one algorithm is significantly faster than the other.

Big O Notation ignores constants. This is simply a mathematical way of saying that Big O Notation never includes regular numbers that aren’t an exponent. In our case, what should technically be O( N2 / 2) becomes simply O( N2). Similarly, O( 2N) would become O( N), and O( N / 2) would also become O( N). Even O( 100N), which is 100 times slower than O( N), would also be referred to as O( N).

Although a hash table with one hundred cells is great for avoiding collisions, we’d be using up one hundred cells to store just five pieces of data, and that’s a poor use of memory. This is the balancing act that a hash table must perform. A good hash table strikes a balance of avoiding collisions while not consuming lots of memory. To accomplish this, computer scientists have developed the following rule of thumb: for every seven data elements stored in a hash table, it should have ten cells. So, if you’re planning on storing fourteen elements, you’d want to have twenty available cells, and so on and so forth. This ratio of data to cells is called the load factor. Using this terminology, we’d say that the ideal load factor is 0.7 (7 elements / 10 cells). If you initially stored seven pieces of data in a hash, the computer might allocate a hash with ten cells. When you begin to add more data, though, the computer will expand the hash by adding more cells and changing the hash function so that the new data will be distributed evenly across the new cells. Luckily, most of the internals of a hash table are managed by the computer language you’re using. It decides how big the hash table needs to be, what hash function to use, and when it’s time to expand the hash table.

when number is 0, our code will not call the countdown() function again, but instead just return, thereby preventing another call of countdown(). In Recursion Land (a real place), this case in which the method will not recurse is known as the base case.

here’s the process you need to know for reading recursive code: 1. Identify what the base case is. 2. Walk through the function assuming it’s dealing with the base case. 3. Then, walk through the function assuming it’s dealing with the case immediately before the base case. 4. Progress through your analysis by moving up the cases one at a time.

we’ve encountered a number of sorting algorithms, including Bubble Sort, Selection Sort, and Insertion Sort. In real life, however, none of these methods are actually used to sort arrays. Most computer languages have built-in sorting functions for arrays that save us the time and effort from implementing our own. And in many of these languages, the sorting algorithm that is employed under the hood is Quicksort.

if we wanted to find the median grade. The obvious way to solve this would be to sort the entire array and then jump to the appropriate cell. Even were we to use a fast sorting algorithm like Quicksort, this algorithm would take at least O( N log N) for average cases, and while that isn’t bad, we can do even better with a brilliant little algorithm known as Quickselect. Quickselect relies on partitioning just like Quicksort, and can be thought of as a hybrid of Quicksort and binary search. As we’ve seen earlier in this chapter, after a partition, the pivot value ends up in the appropriate spot in the array. Quickselect takes advantage of this in the following way: Let’s say that we have an array of eight values, and we want to find the secondto-lowest value within the array. First, we partition the entire array: After the partition, the pivot will hopefully end up somewhere towards the middle of the array: This pivot is now in its correct spot, and since it’s in the fifth cell, we now know which value is the fifth-lowest value within the array. Now, we’re looking for the second-lowest value. But we also now know that the second-lowest value is somewhere to the left of the pivot. We can now ignore everything to the right of the pivot, and focus on the left subarray. It is in this respect that Quickselect is similar to binary search: we keep dividing the array in half, and focus on the half in which we know the value we’re seeking for will be found.

A binary tree is a tree that abides by the following rules: • Each node has either zero, one, or two children. • If a node has two children, it must have one child that has a lesser value than the parent, and one child that has a greater value than the parent.

The algorithm for searching within a binary tree begins at the root node: 1. Inspect the value at the node. 2. If we’ve found the value we’re looking for, great! 3. If the value we’re looking for is less than the current node, search for it in its left subtree. 4. If the value we’re looking for is greater than the current node, search for it in its right subtree.

the algorithm for deletion from a binary tree is: • If the node being deleted has no children, simply delete it. • If the node being deleted has one child, delete it and plug the child into the spot where the deleted node was. • When deleting a node with two children, replace the deleted node with the successor node. The successor node is the child node whose value is the least of all values that are greater than the deleted node.–If the successor node has a right child, after plugging the successor node into the spot of the deleted node, take the right child of the successor node and turn it into the left child of the parent of the successor node.

While the Facebook and Twitter examples are similar, the nature of the relationships in each example are different. Because relationships in Twitter are one-directional, we use arrows in our visual implementation, and such a graph is known as a directed graph. In Facebook, where the relationships are mutual and we use simple lines, the graph is called a non-directed graph. While a simple hash table can be used to represent a graph, a more robust object-oriented implementation can be used as well.

There are numerous algorithms for solving the shortest path problem, and one really interesting one was discovered by Edsger Dijkstra (pronounced “dike’ struh”) in 1959. Unsurprisingly, this algorithm is known as Dijkstra’s algorithm. Here are the rules of Dijkstra’s algorithm (don’t worry—they’ll become clearer when we walk through our example): 1. We make the starting vertex our current vertex. 2. We check all the vertices adjacent to the current vertex and calculate and record the weights from the starting vertex to all known locations. 3. To determine the next current vertex, we find the cheapest unvisited known vertex that can be reached from our starting vertex. 4. Repeat the first three steps until we have visited every vertex in the graph. Let’s walk through this algorithm step by step.