Welcome to Programming and Data Structures

There are multiple reasons why we might need to understand and describe the efficiency of a given algorithm. Perhaps we want to estimate how long a program will take to run on a large data set. Or maybe we are trying to decide between two different algorithms to solve the same problem and want to pick the one that will perform better.

While attempting to describe the efficiency of an algorithm, there are many different things we could measure about an algorithm: the number of lines of code to express, the amount of memory used while running, the time it takes to run, etc.... By some definition, each of those is a measure of efficiency and is something we might care about.

As users of a program, what we usually care about is “How quickly do I get my answer”. A search for a file on your computer that shows results in 0.02 seconds is great; a search that takes 20 minutes would be much less useful. So the metric that we generally focus on is time efficiency. “How long does it take to finish an algorithm?”

However, the time to do something depends on many factors - how fast is the computer? how many other things is it trying to do? how big is the problem (how many files are there to search)? These factors will change depending on who is running the program and when; the fact that you are running a program on a faster computer and it takes less time than when I run it does not tell us anything interesting about the algorithm the program uses.

So instead of measuring time when measuring algorithms, we usually think in terms of the “work” required to do a job of size n. The work required to perform a particular algorithm does not generally change when it is executed on different machines or under different conditions. Those conditions may affect how much time it takes to do a certain amount of work. A faster computer can do more work in the same amount of time. A computer that is busy doing other things may take longer to do the same amount of work. However even as the time to do a set amount of work changes, the amount of work to be done remains the same.

The amount of work is affected by how big a job we are doing. Searching through 100,000 files involves more work than searching through 10 files. So we always do need to qualify our work estimates with \(n\text{:}\) the size of the job. \(n\) can have different meanings for different algorithms, but it always stands for “the size of the job being done”. If we are sorting numbers, \(n\) would be the number of numbers to sort. If we are finding the median score on a set of tests, \(n\) would be the number of tests being analyzed.

Learning to identify what definition for \(n\) makes the most sense for a given algorithm is an important skill. There often might be multiple reasonable choices for what \(n\) could be. For example, if we are searching for a word in a document, is \(n\) the number of words in the document? the number of characters? the number of lines? Each of those choices could be justified. However, some choices will lead to more useful analyses than others. In this case, choosing \(n\) to be the number of words in the document is likely to lead to a more useful analysis than choosing the number of lines, since documents can vary widely in how many words are on each line. Choosing the number of characters would also be reasonable, but would likely lead to more complex analyses without adding much value over simply counting words.

Sometimes we may need to consider more than one number in analyzing an algorithm. For instance, to identify the closest group of people to each individual in a social network, we likely need to know something about the number of people and the average number of connections between a single person and others in the network. In those cases, we will use n, m, etc... to represent all of the important numbers.