A Common-Sense Guide to Data Structures and Algorithms

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.