Skip to main content

Section 3.17 Algorithm Efficiency (2026)

90 minutes
In this lesson we are going to use an App Inventor app to analyze the algorithms we have been studying. You will be running two different apps, one to test the search algorithms and one to test the sorting algorithms.
Another way to look at this activity is as quality assurance (QA). Many careers in the computing field start with assignments in QA. This is where you help software developers test and debug their apps.

Subsection 3.17.1 Analyzing Search Algorithms

Watch the following presentation on analyzing search algorithms to learn how to determine how fast linear search and binary search are. The code in the video is from MIT App Inventor, but the concepts apply to any programming language.
You will be using the Linear vs Binary Search Comparison app below to analyze the search algorithms. The app will run both search algorithms on a list of numbers and record the time it takes to find a number in the list. You will be able to generate random lists with different lengths and record the results. Note that the binary search algorithm will only work on sorted lists, so the app will generate a sorted list every time.

Activity 3.17.2 Linear vs. Binary Search Trade-offs.

Subsection 3.17.2 Analyzing Sort Algorithms

Sorting algorithms are a little more complicated to analyze than search algorithms. The time it takes to sort a list depends on the number of items in the list, the order of the items in the list, and the algorithm used to sort the list.
Watch this Ted-Ed video to learn about three different sorting algorithms and how they work. (There are actually many more sorting algorithms.)
Watch the following presentation on analyzing sort algorithms to learn how to determine how fast bubble sort, merge sort and bucket sort are.

Subsection 3.17.3 Algorithm Efficiency Review

Activity 3.17.3 Algorithm Efficiency Vocabulary.

Activity 3.17.4.

If you were using binary search to find the number 14 in the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], how many iterations would be required to find 14 in the list?
  • 3
  • Correct! Step 1 checks 8, step 2 checks 12, and step 3 checks 14, so the search stops on the third iteration.
  • 2
  • Incorrect.
  • 14
  • Incorrect. Linear search would take 14 steps, but binary search divides the list in half each step.
  • 4
  • Incorrect. The search finds 14 on the third iteration and stops immediately.

Activity 3.17.5.

The function shown in this graph is known as the base-2 logarithm function, y = log2(x). Which search algorithm behaves like this function?
  • Sequential search
  • Incorrect. Sequential search grows linearly, y = x.
  • Binary search
  • Correct! Binary search has logarithmic time complexity, y = log2(x).

Activity 3.17.6.

In talking about sorting algorithms in general, a sort algorithm’s efficiency refers to ______________________.
  • how many swaps are needed to sort the values.
  • Incorrect.
  • how many comparisons are needed to sort the values.
  • Incorrect.
  • whether the algorithm correctly arranges the values in order.
  • Incorrect. That refers to correctness, not efficiency.
  • how long it takes to arrange the values in order.
  • Correct! Algorithmic efficiency measures run-time relative to input size.
  • whether or not the algorithm contains a bug.
  • Incorrect.

Activity 3.17.7.

To say that bucket sort is more efficient than bubble sort means that _________________.
  • bucket sort requires fewer swaps than bubble sort.
  • Incorrect.
  • for any size list, bucket sort will always be faster than bubble sort.
  • Incorrect. For extremely small lists, simple algorithms can sometimes run faster due to lower overhead.
  • as the size of the list grows, bucket sort will be faster than bubble sort.
  • Correct! Efficiency describes how execution time scales as input size (N) increases.
  • bucket sort requires fewer comparisons than bubble sort.
  • Incorrect.

Activity 3.17.8.

Which of the following characteristics is true of bubble sort? Choose all that apply.
  • More efficient than bucket sort.
  • Incorrect. Bubble sort is N^2, which is less efficient than bucket sort.
  • Useful only for sorting numbers.
  • Incorrect. Bubble sort works on any comparable data types.
  • A comparison-based algorithm.
  • Correct! Bubble sort compares adjacent elements.
  • Widely used to sort large data sets.
  • Incorrect. Bubble sort is inefficient for large datasets due to its N^2 time complexity.
  • An N^2 algorithm.
  • Correct! Bubble sort requires up to N^2 comparisons in the worst case.

Activity 3.17.9.

Which of the following characteristics is true of bucket sort? Choose all that apply.
  • More efficient than bubble sort.
  • Correct! Linear time complexity makes bucket sort faster for large input sizes.
  • Useful only for sorting numbers.
  • Incorrect! A bucket sort can be used to sort many items, including laundry and groceries.
  • An N^2 algorithm.
  • Incorrect. Bucket sort is linear, O(N).
  • A comparison-based algorithm.
  • Incorrect. Bucket sort is a distribution-based sort, not comparison-based.
  • A linear algorithm
  • Correct! Bucket sort runs in O(N) linear time under typical conditions.

Activity 3.17.10.

There are 32 students standing in a classroom. Two different algorithms are given for finding the average height of the students.
Algorithm A
  • Step 1: All students stand.
  • Step 2: A randomly selected student writes his or her height on a card and is seated.
  • Step 3: A randomly selected standing student adds his or her height to the value on the card, records the new value on the card, and is seated. The previous value on the card is erased.
  • Step 4: Repeat step 3 until no students remain standing.
  • Step 5: The sum on the card is divided by 32. The result is given to the teacher.
Algorithm B
  • Step 1: All students stand.
  • Step 2: Each student is given a card. Each student writes his or her height on the card.
  • Step 3: Standing students form random pairs at the same time. Each pair adds the numbers written on their cards and writes the result on one student’s card; the other student is seated. The previous value on the card is erased.
  • Step 4: Repeat step 3 until one student remains standing.
  • Step 5: The sum on the last student’s card is divided by 32. The result is given to the teacher.
Which of the following statements is true?
  • Neither Algorithm A nor Algorithm B calculates the correct average.
  • Incorrect.
  • Both Algorithm A and Algorithm B always calculate the correct average.
  • Correct! Both algorithms sum all 32 heights correctly (one sequentially, one in parallel pairs) and divide by 32.
  • Algorithm B always calculates the correct average, but Algorithm A does not.
  • Incorrect.
  • Algorithm A always calculates the correct average, but Algorithm B does not.
  • Incorrect.
You have attempted of activities on this page.