Big-O Fundamentals: Understanding Time u0026 Space Complexity Quiz

Challenge your understanding of Big-O notation, time complexity, and space complexity concepts. This quiz explores key principles of algorithm analysis, helping you assess your grasp of time and space efficiency in programming.

1. Interpreting Constant Time

   Which Big-O notation denotes an algorithm whose execution time remains constant, regardless of the input size?

   1. O(n^2)
   2. O(n)
   3. O(1)
   4. O(log n)

   Explanation: O(1) describes constant time complexity, meaning the operation takes the same amount of time no matter how large the input is. O(n) is linear and grows directly with input size, O(n^2) indicates quadratic growth where processing time increases rapidly with larger inputs, and O(log n) is logarithmic, which grows more slowly than linear. Only O(1) is truly independent of input size.

2. Comparing Growth Rates

   When input size doubles, which complexity class out of the following increases its number of steps by four times?

   1. O(n)
   2. O(log n)
   3. O(1)
   4. O(n^2)

   Explanation: O(n^2), or quadratic complexity, means that if the input size doubles, the operation count grows four times, since (2n)^2 = 4n^2. O(n) would only double as the input doubles, O(log n) increases by a small constant, and O(1) does not increase at all. Thus, quadratic complexity is the only option that quadruples with input doubling.

3. Recognizing Logarithmic Complexity

   Which of the following best represents an algorithm with time complexity O(log n)?

   1. A loop that processes every element once
   2. A loop that cuts the input size in half each iteration
   3. An operation independent of the input
   4. A nested loop over the entire array

   Explanation: A loop that halves the input each time demonstrates logarithmic, or O(log n), behavior because the number of steps increases slowly as the input size grows. Processing every element is an O(n) operation, nested loops typically result in O(n^2), and operations with no input dependency are O(1). Therefore, only the halving loop matches O(log n).

4. Understanding Space Complexity

   If an algorithm requires allocating a new array of the same size as its input, what is its space complexity?

   1. O(n)
   2. O(n^2)
   3. O(1)
   4. O(log n)

   Explanation: O(n) space complexity means that the memory required grows linearly with the size of the input, which happens when allocating an array the same size as the input. O(1) would mean a fixed amount of memory regardless of input size, O(n^2) would mean memory grows quadratically (such as a two-dimensional array), and O(log n) is much smaller, typical for recursive algorithms with limited stack depth. The linear relationship in this scenario makes O(n) the right choice.

5. Identifying Dominant Terms in Big-O

   Given a function with time complexity expressed as O(n^2 + n), which term determines the Big-O classification as input grows large?

   1. O(n)
   2. O(n + n^2)
   3. O(n^2)
   4. O(2n)

   Explanation: For large input sizes, the term with the highest growth rate dominates Big-O notation, so O(n^2) overshadows O(n). O(n) becomes negligible by comparison as n increases. O(n + n^2) is not standard form and simplifies to O(n^2), while O(2n) is linear and does not fit the scenario described. Therefore, O(n^2) is the correct answer.