Classifying Algorithms
BH and MF: keep page appended to end of 5.1.2 (page 3) with some yellowboxing the whitetext; drop #3-5; keep #7 and 6 in reversed order (need to say "unreasonable for large inputs"
Brian, after we review my changes below, we should address both of these:
- There is a lot of commented-out content on this page. If it's not needed, it should be removed. --MF, 12/20/17
PG: Scrap. If AP still requires it, we must, but I'm not in love with this.
BH: Item 87 of isn't a great example, even though true, because the time depends on how the list was constructed. Also, add n log n.
MF: so much text; I think we are overdoing this idea. Much could be yellowboxed.
On this page, you will learn that some correct algorithms take too long to be practical.
-
This feels repetitive even though the task actually isn't. --MF, 3/11/19
If it isn't already open, load the project U5L3-timer from the previous page. You will be experimenting with time function with each of these input functions:
For each one, what happens to the running time if you double the size of the input?
What does it mean to double the size of the input for numbers from () to ()?
You can classify algorithms by the amount of time they take to run.
I want to put the two definitions in vocab box(es) and to yellowbox-hint all the efficiency categories. --MF, 9/26/18
BH and MF agreed to focus on polynomial vs. exponential and on clarifying what exponential means (since many people get it wrong), and then to say, oh BTW, the college board calls this reasonable and unreasonable. --MF, 3/22/19
To classify an algorithm, look at the number of steps it takes to complete the algorithm, compared to the size of the input.
-
Reasonable Time: If the number of steps is less than or equal to a power of the size of the input, then the algorithm takes polynomial time.
Polynomial time includes constant (n0), sublinear, linear (n1), quadratic (n2), cubic (n3), etc. functions:
| algorithm efficiency |
If you double the size of input,
the time... |
example algorithm |
| constant |
stays the same (multiplies by 20 which is 1) |
item (87) of () |
| sublinear |
multiplies by some number between 1 and 2 (between 20 and 21) |
binary search: position of () in sorted list |
| linear |
multiplies by 2 (which is 21) |
linear search: position of () in unsorted list |
| quadratic |
multiplies by 4 (which is 22) |
some kinds of sorting algorithms |
| cubic |
multiplies by 8 (which is 23) |
some gene mapping algorithms used in biology |
It's rare to find polynomial time algorithms that take more than cubic (n3) time.
What if an algorithm takes an amount of time that's between two categories?
These categories say that an algorithm takes at most so much time. So, for example, a constant-time algorithm is also a linear-time algorithm, and also a polynomial-time algorithm. But usually if someone says an algorithm "takes quadratic time," they mean that it takes more than linear time but not more than quadratic time.
-
Unreasonable Time: If the number of steps is more than any power of the size of the input (that is, more than any polynomial function), then the algorithm takes an unreasonable amount of time.
The classic example of an unreasonable time algorithm is one that takes exponential (2n) time. Just adding 1 to the input size (n) doubles the number of steps!
One kind of problem whose solution often ends up unreasonable is an optimization problem (such as "find the best" or "find the smallest").
This feels more important than we are giving time for. --MF, 3/11/19
It's important to recognize that an unreasonable-time algorithm
still solves a problem correctly. Unreasonable-time algorithms can sometimes be replaced by
heuristics, which are polynomial-time algorithms that don't solve the problem exactly, but give a good enough approximation.
One reason it's worth learning these categories is that in writing programs, you often need to solve a problem for which there are already established solutions. For example, you've learned that searching for something in an unordered list takes linear time, but if the list is sorted, you can search it faster (in sublinear time). So when you're writing a program that needs to search through a list repeatedly, you'll know that it's worthwhile to sort the list before the searching. Knowing about standard algorithms that already exist can help you construct new algorithms.
No one is going to do this. We need more direction. --MF, 3/11/19
- Look at some algorithms you've built. Determine whether each algorithm runs in constant time, sublinear time, linear time, quadratic time, or unreasonable time.
Need to decide what to do here since the graphing labs are being replaced. --MF, 3/11/19
- For Alphie's way of adding integers, create a graph with the number of integers on the horizontal and the runtime on the vertical. Generate data for the graph by running
time function with large inputs to Alphie's way (say, multiples of 100). Then use the techniques from Lab 2 to plot the graph.
- What information does this graph tell you about Alphie's algorithm? Is it constant time, linear time, other polynomial time, or is it unreasonable time?
Do we need all the commented out content here and elsewhere on this page? --MF, 9/26/18
I suggest swapping the order of these two problems so that the paragraph writing isn't lost and also so that idea is closer to the content about it (rather than having a big block of slightly less conected content in between. --MF, 3/11/19
-
This question is similar to those you will see on the AP CSP exam.
The table below shows the computer time it takes to complete various tasks on the data of different sized towns.
| Task |
Small Town
(population 1,000) |
Mid-sized Town
(population 10,000) |
Large Town
(population 100,000) |
| Entering Data |
2 hours |
20 hours |
200 hours |
| Backing up Data |
0.5 hours |
5 hours |
50 hours |
| Searching through Data |
5 hours |
15 hours |
25 hours |
| Sorting Data |
0.01 hour |
1 hour |
100 hours |
Based on the information in the table, which of the following tasks is likely to take the
longest amount of time when scaled up for a city of population 1,000,000.
Entering data
As the population size is multiplied by 10, the time needed for entering data is also multiplied by 10, so for a population of 1,000,000, it should take about 10×200=2000 hours.
Backing up data
As the population size is multiplied by 10, time needed for backing up data is multiplied by 10, so for a population of 1,000,000, it should take about 10×50=500 hours.
Searching through data
Searching through the data seems to go up by about 10 hours each time the population is multiplied by 10, so for a population of 1,000,000, it should take about 35 hours.
Sorting data
Correct! As the population size is multiplied by 10, the time needed for the sorting of data is multiplied by 100. So, for a population of 1,000,000, it should take about 100×100=10,000 hours.
- Write a paragraph explaining the difference between algorithms that run in a reasonable time and algorithms that require unreasonable time to run.
(as you saw on Unit 3 Lab 4: Building a Graphing App)
(as you saw on Unit 5 Lab 1: List Processing Algorithms)
(as you saw on Unit 5 Lab 3: Comparing Algorithms)
block to build the following two blocks in Snap!. Then, determine which block's algorithm can be executed in a reasonable time, and which cannot.
