Main content
AP®︎/College Computer Science Principles
Course: AP®︎/College Computer Science Principles > Unit 4
Lesson 2: Evaluating algorithmsCategorizing run time efficiency
AP.CSP:
AAP‑4 (EU)
, AAP‑4.A (LO)
, AAP‑4.A.3 (EK)
, AAP‑4.A.4 (EK)
, AAP‑4.A.7 (EK)
It's important to understand the run time efficiency of the algorithms we use. When a computer takes too long to solve a problem, it costs more money and deprives the computer of time to spend on other valuable problems. Plus, if the algorithm is used inside a user-facing app, it may result in frustrated users who give up on the app entirely.
Categorizing run times
We can categorize the run time of an algorithm according to how the number of steps increases as the input size increases. Does it always take the same amount of time? That's a constant increase, a very fast run time. Does it always require looking at every possible permutation of the input? That's an exponential increase, a very slow run time. Most run times are somewhere between.
Constant time
When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.
As an example, consider accessing the first element of a list:
firstPost ← posts[1]Even if the list grows to be a million items long, that operation will always require a single step.
We can visualize that relationship as a table:
| List size | Steps |
|---|---|
| 1 | 1 |
| 10 | 1 |
| 100 | 1 |
| 1000 | 1 |
We can also visualize it as a graph:
A constant run time is ideal, but is typically not possible for algorithms that process multiple pieces of data.
Logarithmic time
When an algorithm runs in logarithmic time, it increases proportionally to the logarithm of the input size.
The binary search algorithm is an algorithm that runs in logarithmic time. Read the measuring efficiency article for a longer explanation of the algorithm.
Here's the pseudocode:
PROCEDURE searchList(numbers, targetNumber) {
minIndex ← 1
maxIndex ← LENGTH(numbers)
REPEAT UNTIL (minIndex > maxIndex) {
middleIndex ← FLOOR((minIndex+maxIndex)/2)
IF (targetNumber = numbers[middleIndex]) {
RETURN middleIndex
} ELSE {
IF (targetNumber > numbers[middleIndex]) {
minIndex ← middleIndex + 1
} ELSE {
maxIndex ← middleIndex - 1
}
}
}
RETURN -1
}The algorithm uses a loop to look at multiple items in the list, but crucially, it does not look at every item in the list. Specifically, it looks at log, start base, 2, end base, n items, where n is the number of items in the list.
We can visualize that relationship in a table:
| List size | Steps |
|---|---|
| 1 | 1 |
| 10 | 4 |
| 100 | 7 |
| 1000 | 10 |
We can also see that as a graph:
The number of steps is definitely increasing as input size increases, but at a very slow rate.
Linear time
When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.
The aptly-named linear search algorithm runs in linear time.
The pseudocode shows its simplicity compared to binary search:
PROCEDURE searchList(numbers, targetNumber) {
index ← 1
REPEAT UNTIL (index > LENGTH(numbers)) {
IF (numbers[index] = targetNumber) {
RETURN index
}
index ← index + 1
}
RETURN -1
}This time, the loop looks at every item in the list. This exhaustive search is necessary to search for items in an unsorted list, since there's no way to narrow down where a particular item might be. This algorithm will always require at least as many steps as items in the list.
We can see that in table form:
| List size | Steps |
|---|---|
| 1 | 1 |
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
Or as a graph:
Quadratic time
When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared.
Several list sorting algorithms run in quadratic time, like selection sort. That algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value.
Here's pseudocode for selection sort:
i ← 1
REPEAT UNTIL (i > LENGTH(numbers)) {
minIndex ← i
j ← i + 1
// Find next smallest value
REPEAT UNTIL (j > LENGTH(numbers)) {
IF (numbers[j] < numbers[minIndex]) {
minIndex ← j
}
}
// Swap if new minimum found
IF (minIndex != i) {
tempNum ← numbers[minIndex]
numbers[i] ← tempNum
numbers[minIndex] <- tempNum
}
}The important thing to notice about the algorithm is the nested loop: it loops through each items in the list, and loops again through the remaining items for each of those items. In this case, the algorithm ends up looking at start fraction, 1, divided by, 2, end fraction, left parenthesis, n, squared, minus, n, right parenthesis values, where n is the number of items in the list.
This table shows how many items it'd examine for lists of increasing sizes:
| List size | Steps |
|---|---|
| 1 | 1 |
| 10 | 45 |
| 100 | 4950 |
| 1000 | 499500 |
Here's what that looks like in graph form:
Both the table and the graph show that the number of steps for this algorithm increases at a much faster rate than the previous ones.
Exponential time
When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size.
An algorithm often requires superpolynomial time when it must look at every permutation of values. For example, consider an algorithm that generates all possible numerical passwords for a given password length.
For a password length of 2, it generates 100 passwords:
00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99 That algorithm requires at least 10, squared steps, since there are 10 possibilities for each digit (0-9) and it must try out every possibility for each of the 2 digits.
For any given password length of n, the algorithm requires 10, start superscript, n, end superscript steps. That run time increases incredibly quickly, since each additional digit requires 10 times the number of steps.
This table shows how fast that grows for just the first 5 digits:
| Digits | Steps |
|---|---|
| 1 | 10 |
| 2 | 100 |
| 3 | 1000 |
| 4 | 10000 |
| 5 | 100000 |
Here's what that looks like as a graph:
All together now
Now that we've seen examples of possible run times for algorithms, let's compare them on a graph:
That graph makes it even more clear that there's a definite difference in these run times, especially as input size increases. Since modern computer programs increasingly deal with large data sets (like from millions of users or sensors), the run time efficiency matters quite a bit.
Polynomial vs. superpolynomial
Computer scientists often classify run times into two classes:
- Polynomial time describes any run time that does not increase faster than n, start superscript, k, end superscript, which includes constant time (n, start superscript, 0, end superscript), logarithmic time (log, start base, 2, end base, n), linear time (n, start superscript, 1, end superscript), quadratic time (n, squared), and other higher degree polynomials (like n, cubed).
- Superpolynomial time describes any run time that does increase faster than n, start superscript, k, end superscript, and includes exponential time (2, start superscript, n, end superscript), factorial time (n, !), and anything else faster.
Why do we make the split between polynomial and superpolynomial?
This table of run times illustrates why:
| 10 | 50 | 100 | 300 | 1000 | |
|---|---|---|---|---|---|
| 5, n | 50 | 250 | 500 | 1500 | 5000 |
| n, squared | 100 | 2500 | 10000 | 90000 | |
| n, cubed | 1000 | 125000 | |||
| 2, start superscript, n, end superscript | 1024 | ||||
| n, ! |
Those numbers have no units, so an n, ! algorithm may run in 3.6 million nanoseconds for an n of 10, which is less than a second. For an n of 50, it'd run in 3, times, 10, start superscript, 64, end superscript nanoseconds—but there have only been 10, start superscript, 26, end superscript nanoseconds since the Big Bang! A superpolynomial run time often requires more time than available in the universe, even for relatively small input sizes.
This is why we think of polynomial run times as reasonable and superpolynomial times as unreasonable. A polynomial run time isn't always ideal (and we often try to improve those times), but it is at least feasible.
Computer scientists concentrate their efforts on finding polynomial time algorithms for the problems that currently require superpolynomial time, since that's where the difference matters the most.
Further learning
"Asymptotic analysis" is a more formal method for analyzing algorithmic efficiency. That's not covered here, but if you're interested, you can learn more about Asymptotic analysis from our college-level Algorithms course.
🙋🏽🙋🏻♀️🙋🏿♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!
Want to join the conversation?
I tried to manually implement selection sort with [2, 8, 5, 3, 9, 4, 1] using notepad while keeping track of the variable values. When I arrived at -
'''REPEAT UNTIL (j > LENGTH(numbers)) {
IF (numbers[j] < numbers[minIndex]) {
minIndex ← j
}'''
, I realized that this loop has no expression that increments 'j' so I presumed that it will infinitely run by that loop. Then, I stopped evaluating the algorithm and just scanned over the following lines of code. In the block -
'''IF (minIndex != i) {
tempNum ← numbers[minIndex]
numbers[i] ← tempNum
numbers[minIndex] <- tempNum
}'''
, given that 'tempNum ← numbers[minIndex]', isn't it that 'numbers[minIndex] <- tempNum' will evaluate to 'numbers[minIndex] <- numbers[minIndex]'? I think the values didn't swap correctly. But this is just mere eyeballing of the code and not practically evaluating it. So there's a high chance that I'm actually wrong about my observations, and I'm really sorry if that's the case.(9 votes)
Do I need to attend a college-level Algorithms course if my goal is to become a web developer? Or it isn't necessary for beginning a career in this field?(1 vote)
It's not generally necessary, no. If your goal is to become a web developer, I would concentrate on learning web development skills and developing a portfolio of projects, like creating apps for hackathons or websites for local non-profits. You may find that you will be asked algorithm questions during an interview, but that is highly dependent on the company. For frontend development, I find that practical performance concerns come up more often than algorithmic complexity concerns (but those concerns do intertwine! ).
If you do find the time to learn more algorithms: My friend Bianca teaches algorithms and data structures for JavaScript developers on the website Frontend Masters, that might be something to explore as a way to learn those topics. You can also learn some of that here, in our other Algorithms course, under the Computer Science section.(12 votes)
I literally cannot understand these massive blocks of words(6 votes)
What is n^k? n is any number, right? So then what is k and why is it relevant in terms of polynomial and superpolynomial time?(1 vote)- Yes, k is any positive integer. The difference between n^k and k^n is best understood by noting that "n" is the input size. Putting the input in the exponent (for super polynomial) creates exponential growth. In contrast, polynomial growth puts a fixed k in the exponent.
Hope that helps!(4 votes)
- The paragraph for Linear Time states "This algorithm will always require at least as many steps as items in the list." Shouldn't this be "at most" instead of "at least", because more often than not the element will not be at the end of the list and thus be found earlier? Or did I misunderstood that part?(2 votes)
You are correct, the algorithm will require at most as many steps as items in the list given that the item will likely be found before the end of the list.(0 votes)
- For the Quadratic time selection sort pseudocode example, I don't see any incremental increase for i or j. Wouldn't that mean that the algorithm wouldn't work properly? Otherwise I'm not sure what I'm missing.(1 vote)
- There is an error for the 100 passwords, from the third row onward, the passwords say 21 to 29.(0 votes)
Can you make the pseudocode more readable, as in change some of the symbols to the most common things like changing the arrows to equal signs? I find it hard to follow and I'm basically learning a completely new language when it is intended to be understandable and close to English. I'll probably get used to it but it's my suggestion.(0 votes)- Thank you for your comment, but there are reasons why certain symbols are used instead of others. For example, the arrow is used instead of an equal sign to emphasize that the value on the right is being assigned to the variable on the left and is not just being compared to it.(2 votes)
- When you aren't in the lesson page (here), and click on this article, it has a lot of mysterious overflow to the right. Basically, a horizontal scrollbar pops up and allows you to scroll a lot to the right - so I am figuring that you forgot to add
overflow-x: hidden;or something like that?(0 votes) - At What age/grade are you supposed to learn computer science in? I am not american and have no idea when im going to learn this? anyone??(0 votes)
