Algorithm efficiency basics (fast vs slow) in Intro to Computing - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Algorithm Speed with Real-Life Analogy

Imagine you have two ways to find a book in a library:

• Method A: You check every book one by one from the first shelf to the last.
• Method B: You use the library's index to go directly to the shelf where the book is.

Which method is faster and why?

A Both methods take the same time because you have to look at the book eventually.

B Method B is faster because it uses a shortcut to find the book quickly.

C Method A is faster because you see every book and won't miss it.

D Neither method works because books are randomly placed.

💡 Hint

Think about how using a map or index helps you reach your destination faster.

Method B is faster because it uses an index (like a map) to jump directly to the right place, avoiding checking every book.

❓ trace

intermediate

Trace the Number of Steps in Two Algorithms

Given a list of 5 numbers: [3, 7, 2, 9, 5]

Algorithm 1: Check each number to see if it is 9.

Algorithm 2: Sort the list first, then check if 9 is the last number.

How many steps does each algorithm take to find the number 9?

Intro to Computing

lst = [3, 7, 2, 9, 5]

# Algorithm 1
for num in lst:
    if num == 9:
        break

# Algorithm 2
sorted_list = sorted(lst)
if sorted_list[-1] == 9:
    pass

A Algorithm 1 takes 4 steps; Algorithm 2 takes 6 steps.

B Algorithm 1 takes 9 steps; Algorithm 2 takes 3 steps.

C Algorithm 1 takes 3 steps; Algorithm 2 takes 10 steps.

D Algorithm 1 takes 5 steps; Algorithm 2 takes 5 steps.

💡 Hint

Count how many numbers are checked before finding 9 in Algorithm 1. For Algorithm 2, consider sorting steps plus the check.

Algorithm 1 checks numbers until it finds 9 at the 4th step. Algorithm 2 sorts the list (which takes multiple steps, simplified here as 5 steps) plus 1 step to check the last number, totaling 6 steps.

❓ Comparison

advanced

Comparing Algorithm Growth Rates

Which algorithm will be faster for very large input sizes?

Algorithm X: Runs in time proportional to n (linear time).

Algorithm Y: Runs in time proportional to n squared (quadratic time).

A Algorithm Y is faster for small inputs but slower for large inputs.

B Both algorithms run at the same speed for large inputs.

C Algorithm X is faster because its time grows slower as input size increases.

D Algorithm Y is faster because it does more work per step.

💡 Hint

Think about how doubling the input size affects each algorithm's steps.

Algorithm X grows linearly, so doubling input doubles time. Algorithm Y grows quadratically, so doubling input quadruples time. For large inputs, Algorithm X is faster.

❓ identification

advanced

Identify the Algorithm Type from Description

An algorithm checks every pair of items in a list to find duplicates. If the list has n items, it compares each item with every other item.

What is the time complexity of this algorithm?

A O(n squared)

B O(n log n)

C O(n)

D O(1)

💡 Hint

Think about how many pairs are in a list of n items.

Checking every pair means comparing n items with n-1 others, roughly n*n = n squared comparisons.

🚀 Application

expert

Choose the Most Efficient Algorithm for Large Data

You need to search for a name in a phone book with 1 million entries.

Which method is the most efficient?

A Sort the phone book first, then look for the name.

B Randomly pick names until you find the target.

C Look at each name from the start until you find the target (linear search).

D Use a binary search on the sorted phone book.

💡 Hint

Think about how dividing the search space helps find the target faster.

Binary search works on sorted data and cuts the search space in half each step, making it very fast for large data.