Measuring the Efficiency of an Algorithm

Data structures, which allow data within a program to be organized and structured, are one of the most essential elements of all programming. Popular examples of data structure types include lists, stacks, queues, and trees. Algorithms are what animate those data structures and allow them to be manipulated. For instance, if you want your program to sort data or search through data, you would utilize a sort or search algorithm alongside your chosen data structure.

Multiple factors go into one's choice of algorithm in a program. It is important to remember that algorithms are not "one size fits all", and that an algorithm that may be perfect in one scenario may be useless in another. Two of the foremost ways an algorithm's efficiency is measured are by its time complexity and space complexity. Time complexity refers to the overall time an algorithm may take to complete all of its functions based on its input. On the other hand, space complexity refers to the total memory taken up by the algorithm. Consider this: it would be fair to say that a program's speed will be a primary concern of most programmers, but memory limitations may impact what algorithms can or cannot be used. What if an algorithm has a favorably low time complexity but a space complexity that is untenable for your environment? This is one simple example of a dilemma a programmer may face when choosing an algorithm for their program.

To better demonstrate, let's look at a simple linear search algorithm. With a linear search, the search begins at the top of a structure, and the algorithm reviews every element until the searched item is found. In terms of space complexity, the algorithm will only use as much space as the input requires, meaning no additional space is needed. Complexity can be expressed in "big O notation": the space complexity here can be expressed as O(1), indicating the space is constant relative to the input.

Looking at just the space complexity, this may seem like a decent choice thus far, as this algorithm would not require any extra space to implement. The time complexity of this algorithm is where problems may arise. In big O notation, the time complexity of a linear search algorithm can be expressed as O(N), where N is the number of items in the data structure being searched. Put another way: the bigger our data structure is, the more time it takes for the algorithm to complete its jobs. A linear search algorithm may be acceptable if the list we are searching is relatively small, and the program may conceivably be able to review each item in the list in a reasonable amount of time. If we look at a list of 50 items and our search string happens to be item #50, most modern computers will still return this result relatively fast. But what if our data structure has tens or hundreds of thousands of items? The time and effort it takes to review every single item in the structure may become untenable if the searched item is at the bottom. Therefore, the time complexity considerations would make a linear search algorithm unfavorable if dealing with a larger data structure.

When a programmer is writing a relatively simple program - for instance, a macro that automates a specific repetitive function within their job - considerations of time & space complexity may be less critical, as the low complexity of the data structure could never require a more complex algorithm. On the other side of this - say, a database program that holds personal information for thousands of customers - you would likely not use the same algorithm you would use in the former example, since you would be dealing with far larger and more complicated data structures. Applying the most efficient algorithm for a given end use is vital to program design.