CS: Big-O Notation and Algorithm Efficiency
Comparing how algorithms grow as input size increases
CS: Big-O Notation and Algorithm Efficiency
Comparing how algorithms grow as input size increases
CS - Grade 9-12
- 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.
Think about how the number of steps changes when the list size doubles.
The time complexity is O(n). The running time grows directly with the number of items because the algorithm visits each item one time. - 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.
The time complexity is O(1). The algorithm does the same amount of work regardless of the size of the input list. - 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.
Multiply the number of outer loop steps by the number of inner loop steps.
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. - 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.
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. - 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).
Fastest growing means the running time becomes the largest for very large inputs.
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. - 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.
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. - 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.
Big-O focuses on how the running time grows, not exact step counts.
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. - 8
Consider this step count for an algorithm: 5n^2 + 20n + 100. What is the Big-O time complexity? Explain which term matters most.
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. - 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.
Imagine using a nested loop where each student is compared with many other students.
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. - 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.
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. - 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.
When adding different parts of an algorithm, keep the term that grows the fastest.
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. - 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.
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.