CS: Big-O Notation and Algorithm Efficiency Worksheet

Question 1

An algorithm checks each item in a list of n items exactly once. What is its time complexity in Big-O notation? Explain your answer.

Accepted Answer

The time complexity is O(n). The running time grows directly with the number of items because the algorithm visits each item one time.

Question 2

An algorithm prints the first item in a list, no matter how many items are in the list. What is its time complexity in Big-O notation? Explain your answer.

Accepted Answer

The time complexity is O(1). The algorithm does the same amount of work regardless of the size of the input list.

Question 3

A program uses two nested loops. The outer loop runs n times, and for each outer loop step, the inner loop also runs n times. What is the time complexity? Explain how you know.

Accepted Answer

The time complexity is O(n^2). The inner loop runs n times for each of the n outer loop steps, so the total number of operations is n times n.

Question 4

A binary search algorithm repeatedly cuts a sorted list in half until it finds the target value or runs out of values. What is the time complexity of binary search? Explain why.

Accepted Answer

The time complexity is O(log n). Each step cuts the remaining search space in half, so the number of steps grows slowly compared with the input size.

Question 5

Put these Big-O growth rates in order from fastest growing to slowest growing as n becomes very large: O(n), O(1), O(n^2), O(log n).

Accepted Answer

From fastest growing to slowest growing, the order is O(n^2), O(n), O(log n), O(1). Quadratic growth increases the fastest, and constant time does not grow with n.

Question 6

A sorting algorithm takes about n^2 steps in the worst case. If the input size doubles from n to 2n, about how many times more steps will it take? Explain your answer.

Accepted Answer

It will take about 4 times more steps. Since the running time is proportional to n^2, doubling n gives (2n)^2, which equals 4n^2.

Question 7

A loop runs from i = 1 to i = n. Inside the loop, the program performs 10 simple operations. What is the time complexity? Explain why the number 10 does not change the Big-O classification.

Accepted Answer

The time complexity is O(n). The 10 operations are a constant factor, and Big-O notation ignores constant multipliers when describing long-term growth.

Question 8

Consider this step count for an algorithm: 5n^2 + 20n + 100. What is the Big-O time complexity? Explain which term matters most.

Accepted Answer

The time complexity is O(n^2). For large values of n, the n^2 term grows faster than the n term and the constant term, so it dominates the running time.

Question 9

A program compares every pair of students in a class of n students to see if any two have the same birthday. What is the likely Big-O time complexity if it checks all pairs directly? Explain your answer.

Accepted Answer

The likely time complexity is O(n^2). Comparing all pairs requires checking many combinations of two students, and the number of pairs grows roughly with n squared.

Question 10

Two algorithms solve the same problem. Algorithm A is O(n), and Algorithm B is O(n^2). Which algorithm is usually more efficient for very large inputs? Explain your answer.

Accepted Answer

Algorithm A is usually more efficient for very large inputs. A linear algorithm grows much more slowly than a quadratic algorithm as n becomes large.

Question 11

An algorithm first loops through n items once, then later uses a separate nested loop that runs n times inside another n-time loop. What is the overall time complexity? Explain your reasoning.

Accepted Answer

The overall time complexity is O(n^2). The first loop is O(n), but the nested loop is O(n^2), and the faster-growing term dominates the total running time.

Question 12

A student says, "An O(log n) algorithm is always faster than an O(n) algorithm." Explain why this statement is not always true, but why O(log n) is still considered more efficient for large inputs.

Accepted Answer

The statement is not always true because constant factors, hardware, and small input sizes can make an O(n) algorithm faster in a specific situation. However, O(log n) grows more slowly than O(n), so it is generally more efficient as input size becomes very large.

CS: Big-O Notation and Algorithm Efficiency

Related Cheat Sheets

More CS Worksheets

More Grade 9-12 Worksheets