Page 5: Categorizing Algorithms

Unit 5, Lab 1, Page 5

On this page, you will compare four algorithms and learn how they each take a different category of time to run.

1. Locate the block included in your project, and time it for various starting numbers.

   Starting Number	25,000 integers Time
   1000
   10,000
   100,000
   1,000,000
   10,000,000

2. Look at the table. How would you describe what happens to the time as the starting number gets bigger? Write a hypothesis about the pattern.

3. There are several different ways to sort a list, some of which you will learn about in Unit 8. This sort block uses an “insertion sort” algorithm.

   Locate the block included in your project, and time it for each length list.

   Length of List	Sort Time
   10
   100
   1000

4. How would you describe what happens to the time as the size of the input list gets bigger? Write a hypothesis.

You can classify algorithms by the amount of time they take to run.

• An algorithm takes linear time the number of steps is proportional to the input size; doubling the input size doubles the time required.

• An algorithm takes sublinear time if the number of steps grows more slowly than the size.

• An algorithm takes constant time if it takes the same number of steps regardless of input size.

• An algorithm takes quadratic time if the number of steps is proportional to the square of the input size.

5. Look back at your table for linear search. Confirm that multiplying the list length by ten roughly multiplies the time taken by ten (linear time).

6. Look back at your table for binary search. Confirm that the search time for each word list is less than for linear search (sublinear time).

7. Look back at your table for 25,000 integers. Confirm that it takes about the same amount of time regardless of the input (constant time).

8. Look back at your table for sort. Confirm that multiplying the list length by ten roughly multiplies the time taken by one hundred (quadratic time).

The difference between linear search and binary search can be very important if you’re searching in a list of ten million items, but the most important difference in algorithm efficiency is between polynomial time (proportional to any power of the input size) and exponential time.

• An algorithm takes polynomial time if the number of steps is less than or equal to a power of the size of the input, such as constant (n⁰), sublinear, linear (n¹), quadratic (n²), or cubic (n³).
• An algorithm takes exponential time if the number of steps is proportional to an exponential function of the size of the input, such as 2ⁿ, 10ⁿ, etc., which is much slower than any polynomial.

In an exponential time algorithm, just adding 1 to the input size (n) of a 2ⁿ time algorithm doubles the number of steps! So, for example, if the input size is 20, any polynomial time algorithm will be fast enough, but an exponential time algorithm might take many years to finish.

AAP-4.A.7

• The term “reasonable time” describes any algorithm that runs in polynomial time. Exponential time algorithms are not considered reasonable.

On the Internet, many people use the word exponential to mean “happening very fast”, such as clickbait-headline-example-blah or example-bleh. -some nicer version of, now you know better-

AAP-2.M.2 text before bullets

One reason it’s worth learning these categories is to avoid reinventing the wheel. For example, you’ve learned that if a list is sorted you can search it in sublinear time using binary search. So when you’re writing a program that needs to search through a list repeatedly, it’s worthwhile to sort the list before searching. Knowing about algorithms that already exist can help you construct new algorithms.

All of the algorithms you’ve explored so far in this lab (linear search; binary search; 25,000 integers; and sort) are reasonable time algorithms. The following optional activity is an example of an exponential time algorithm.

A problem that may be familiar that requires an exponential time algorithm is computing any given element of Pascal’s Triangle. In Pascal’s Triangle, each number is found by adding the two numbers above it. For example, 4 + 6 = 10 and 15 + 6 = 21 as shown below. The first and last number of each row, which don’t have two numbers above them are 1.

9. Locate the block included in your project, and time it for various inputs.
   

   If these take too long to run, you can stop your program; just fill in the table as far as the speed of your computer will allow.

   Inputs	Pascal’s Triangle Time
   5, 2
   10, 5
   15, 7
   20, 10
   25, 12

   The row value is the input to pascals triangle that matters. (The position input is only given so you get a time for one of the positions near the middle of the row, which take longer to compute.)

   These row inputs are very small compared to the input size for the linear search, binary search, and sort algorithms, and yet the time required for pascals triangle is much higher. Your computer probably can’t do much past 25.

   This algorithm works by adding the two numbers above using the algorithm inside itself recursively, but there are better algorithms that compute the value a number in Pascal’s Triangle in linear time.

10. Write a paragraph explaining the difference between algorithms that run in a reasonable time and those that do not.