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.

Practice

1.

What does algorithm efficiency mainly measure?

easy

A. How fast or slow an algorithm solves a problem

B. The color of the computer screen

C. The size of the computer's hard drive

D. The number of users on a website

Solution

1. Step 1: Understand the meaning of algorithm efficiency

   Algorithm efficiency tells us how quickly or slowly an algorithm completes its task.

2. Step 2: Compare options to the definition

   Only How fast or slow an algorithm solves a problem matches the concept of speed or slowness of solving a problem.

3. Final Answer:

   How fast or slow an algorithm solves a problem -> Option A

4. Quick Check:

   Algorithm efficiency = speed of solving [OK]

Hint: Algorithm efficiency = speed of solving problems [OK]

Common Mistakes:

• Confusing efficiency with hardware specs
• Thinking efficiency is about user count
• Mixing efficiency with unrelated computer parts

2.

Which of these is a sign of a faster algorithm?

for i in range(n):
    print(i)

easy

A. The algorithm jumps directly to the middle item

B. The algorithm checks every item one by one

C. The algorithm repeats the same step many times

D. The algorithm uses more memory than needed

Solution

1. Step 1: Analyze the given code

   The code loops through all items from 0 to n-1, checking each one.

2. Step 2: Compare with options describing speed

   Jumping directly to the middle item is faster than checking all items one by one.

3. Final Answer:

   The algorithm jumps directly to the middle item -> Option A

4. Quick Check:

   Jumping steps = faster algorithm [OK]

Hint: Faster algorithms skip steps, not check all [OK]

Common Mistakes:

• Thinking looping over all items is fast
• Confusing memory use with speed
• Ignoring the benefit of skipping steps

3.

What is the output speed difference between these two algorithms when n is very large?

Algorithm 1: Check every item one by one
Algorithm 2: Jump to the middle, then half repeatedly

medium

A. Algorithm 1 is faster because it checks all items

B. Algorithm 2 is faster because it reduces steps quickly

C. Both algorithms take the same time

D. Algorithm 1 uses less memory so it is faster

Solution

1. Step 1: Understand the two algorithms

   Algorithm 1 checks all items one by one (slow for large n). Algorithm 2 jumps to the middle and halves the search repeatedly (fast for large n).

2. Step 2: Compare efficiency for large n

   Algorithm 2 reduces the number of steps quickly, making it faster than Algorithm 1.

3. Final Answer:

   Algorithm 2 is faster because it reduces steps quickly -> Option B

4. Quick Check:

   Halving steps = faster algorithm [OK]

Hint: Halving steps beats checking all [OK]

Common Mistakes:

• Assuming checking all is faster
• Ignoring step reduction benefits
• Confusing memory use with speed

4.

Find the error in this slow algorithm and suggest a faster approach:

def find_item(lst, target):
    for item in lst:
        if item == target:
            return True
    return False

medium

A. The algorithm has a syntax error in the loop

B. The algorithm uses too much memory; reduce list size

C. The algorithm returns the wrong value

D. The algorithm checks all items; use binary search on sorted list instead

Solution

1. Step 1: Identify the algorithm's behavior

   The function checks each item one by one until it finds the target or ends.

2. Step 2: Suggest a faster method

   Using binary search on a sorted list jumps to the middle and halves the search, making it faster.

3. Final Answer:

   The algorithm checks all items; use binary search on sorted list instead -> Option D

4. Quick Check:

   Linear search slow; binary search fast [OK]

Hint: Replace linear search with binary search for speed [OK]

Common Mistakes:

• Thinking syntax error exists
• Confusing memory use with speed
• Believing return value is wrong

5.

You have a list of 1,000,000 numbers sorted in order. You want to find if the number 500,000 is in the list. Which algorithm is best and why?

hard

A. Randomly pick numbers until you find 500,000

B. Check each number from start to end; simple but slow

C. Use binary search to jump and halve the search area repeatedly

D. Sort the list again before searching

Solution

1. Step 1: Understand the problem and data

   The list is sorted with 1,000,000 numbers; searching for 500,000.

2. Step 2: Evaluate algorithm choices

   Checking each number (Check each number from start to end; simple but slow) is slow. Random picking (Randomly pick numbers until you find 500,000) is unreliable. Sorting again (Sort the list again before searching) wastes time. Binary search (Use binary search to jump and halve the search area repeatedly) uses the sorted order to jump and halve search area, making it fastest.

3. Final Answer:

   Use binary search to jump and halve the search area repeatedly -> Option C

4. Quick Check:

   Sorted list + binary search = fastest search [OK]

Hint: Use binary search on sorted lists for fast lookup [OK]

Common Mistakes:

• Choosing linear search for large sorted lists
• Thinking sorting again helps
• Relying on random guessing