Big-O Notation Beginner Quiz
30 questions on Big O Notation.
Question 1: What is the primary purpose of Big-O Notation in computer science?
- A. To measure the exact execution time of a program in milliseconds
- B. To describe how the runtime or space requirements of an algorithm scale as the input size grows β (correct answer)
- C. To debug code errors
- D. To convert binary to decimal
Explanation: Big-O is a mathematical notation used to classify algorithms according to how their run time or space requirements grow as the input size (n) becomes extremely large.
Question 2: Which Big-O complexity represents "Constant Time"?
- A. O(n)
- B. O(log n)
- C. O(1) β (correct answer)
- D. O(n^2)
Explanation: O(1) means the algorithm takes the same amount of time to execute regardless of the size of the input data.
Question 3: Which of the following operations is an example of O(1) complexity?
- A. Searching for an item in an unsorted array
- B. Sorting an array
- C. Accessing an element in an array by its index (e.g.,
arr[5]) β (correct answer)
- D. Printing all elements of an array
Explanation: Because array elements are stored in contiguous memory, the computer can instantly calculate the exact memory location of arr[5] without iterating through arr[0] to arr[4].
Question 4: Which Big-O complexity represents "Linear Time"?
- A. O(1)
- B. O(n) β (correct answer)
- C. O(n^2)
- D. O(log n)
Explanation: O(n) means the runtime grows directly in proportion to the size of the input. If the input size doubles, the time it takes also doubles.
Question 5: Which of the following operations is an example of O(n) complexity?
- A. A single
for loop iterating through an array from start to finish β (correct answer)
- B. Accessing an array by index
- C. A nested loop (a loop inside a loop) over the same array
- D. Binary Search
Explanation: To print or check every element in an array of size n, the computer must perform n operations.
Question 6: Which complexity represents "Quadratic Time"?
- A. O(n)
- B. O(n log n)
- C. O(n^2) β (correct answer)
- D. O(2^n)
Explanation: O(n^2) means the runtime grows squarely relative to the input size. If the input doubles (2x), the time takes four times longer (4x).
Question 7: What typical code structure often results in O(n^2) time complexity?
- A. A single
while loop
- B. Two separate
for loops, one after the other
- C. A nested loop (e.g., a
for loop inside another for loop, both iterating n times) β (correct answer)
- D. A single
if/else statement
Explanation: For every single iteration of the outer loop (runs n times), the inner loop also runs n times, resulting in n * n = n^2 total operations.
Question 8: Which Big-O complexity represents "Logarithmic Time"?
- A. O(1)
- B. O(log n) β (correct answer)
- C. O(n)
- D. O(n!)
Explanation: O(log n) grows very slowly. It usually indicates an algorithm that cuts the remaining dataset in half with each step, such as Binary Search.
Question 9: If an algorithm runs in O(log n) time, and takes 10 steps to process 1,000 items, roughly how many steps will it take to process 2,000 items?
- A. 20 steps
- B. 100 steps
- C. 11 steps β (correct answer)
- D. 2,000 steps
Explanation: Because logarithmic algorithms halve the data each step, doubling the input size (from 1,000 to 2,000) only adds *one* additional step!
Question 10: When evaluating Big-O, which case do we primarily care about most in computer science?
- A. The Best Case
- B. The Average Case
- C. The Worst Case β (correct answer)
- D. The Random Case
Explanation: We evaluate the worst-case scenario (the maximum possible time an algorithm could take) to guarantee our system won't crash or hang under heavy, difficult loads.
Question 11: In Big-O notation, we drop "constants". Which of the following is the correct reduction of O(2n + 5)?
- A. O(n) β (correct answer)
- B. O(2n)
- C. O(5)
- D. O(n + 5)
Explanation: Big-O focuses on the growth *curve* as n approaches infinity. Constants like 2 or 5 become mathematically insignificant, so O(2n + 5) is simply O(n).
Question 12: If a function has two separate, un-nested loops iterating over the same array of size n, what is the final time complexity?
- A. O(n^2)
- B. O(2n)
- C. O(n) β (correct answer)
- D. O(1)
Explanation: The runtime is strictly n + n = 2n. Dropping the constant 2 leaves us with O(n). Nested loops multiply; sequential loops add.
Question 13: What is "Space Complexity"?
- A. How much space the code takes up on the screen
- B. The amount of extra memory (RAM) an algorithm requires as the input size grows β (correct answer)
- C. The size of the database
- D. The bandwidth of the network
Explanation: If you copy an entire array of size n into a new temporary array, your space complexity is O(n). If you only use a few integer variables regardless of input size, it's O(1) space.
Question 14: Which sorting algorithm is famously known for having an O(n^2) worst-case time complexity?
- A. Bubble Sort β (correct answer)
- B. Merge Sort
- C. Heap Sort
- D. Binary Sort
Explanation: Bubble sort compares every element with every other element adjacent to it, requiring a nested loop that results in O(n^2) time.
Question 15: What is the best possible average time complexity for a comparison-based sorting algorithm (like Merge Sort or Quick Sort)?
- A. O(1)
- B. O(n)
- C. O(n log n) β (correct answer)
- D. O(log n)
Explanation: Mathematically, a general-purpose comparison sort cannot perform better than O(n log n) in the average/worst case.
Question 16: Consider a function that takes an array of size n. It loops through the array, and inside that loop, it does a Binary Search on another sorted array of size n. What is the time complexity?
- A. O(n)
- B. O(log n)
- C. O(n log n) β (correct answer)
- D. O(n^2)
Explanation: The outer loop runs n times. The inner Binary Search runs in log n time. Multiplying them gives O(n log n).
Question 17: Which of the following complexities represents "Exponential Time"?
- A. O(n^2)
- B. O(n^3)
- C. O(2^n) β (correct answer)
- D. O(n!)
Explanation: Exponential time (O(2^n)) doubles the processing time with every single item added to the input. It is extremely slow and usually found in naive recursive solutions (like un-memoized Fibonacci).
Question 18: Which of the following complexities represents "Factorial Time", often called the slowest common complexity?
- A. O(2^n)
- B. O(n^n)
- C. O(n!) β (correct answer)
- D. O(n log n)
Explanation: Factorial time (O(n!)) grows catastrophically fast. It is typically seen in algorithms that generate all possible permutations of a dataset (like the Traveling Salesperson Problem).
Question 19: If an algorithm's complexity is O(n^2 + n + 10), what does it simplify to in Big-O notation?
- A. O(n^2) β (correct answer)
- B. O(n^3)
- C. O(n)
- D. O(10)
Explanation: We always drop non-dominant terms. As n gets huge (e.g., 1,000,000), n^2 becomes so massively large that the + n and + 10 have virtually zero impact on performance.
Question 20: What is the time complexity of pushing an element onto the end of a dynamic array (like a Python List or Java ArrayList), assuming no resize is needed?
- A. O(1) β (correct answer)
- B. O(n)
- C. O(log n)
- D. O(n^2)
Explanation: Because the array keeps track of its current length, adding an item directly to the end does not require shifting any other elements, taking constant time.
Question 21: What is the time complexity of inserting an element at the *front* (index 0) of a standard array of size n?
- A. O(1)
- B. O(n) β (correct answer)
- C. O(log n)
- D. O(n^2)
Explanation: To insert at index 0, every single existing element in the array must be shifted one position to the right in memory to make room, taking O(n) operations.
Question 22: What is the average time complexity of looking up a value in a well-balanced Hash Table (Dictionary)?
- A. O(n)
- B. O(log n)
- C. O(1) β (correct answer)
- D. O(n^2)
Explanation: The hash function calculates the exact memory bucket instantly. Even for millions of records, lookup time remains constant (barring heavy collisions).
Question 23: Which of these correctly lists Big-O complexities from fastest (most efficient) to slowest (least efficient)?
- A. O(1), O(n), O(log n), O(n^2)
- B. O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) β (correct answer)
- C. O(n), O(1), O(n^2), O(log n)
- D. O(2^n), O(n^2), O(n log n), O(n)
Explanation: Constant is best, followed by logarithmic, linear, linearithmic, quadratic, and finally exponential as the worst.
Question 24: If an algorithm takes two separate arrays as input, one of size A and one of size B, and loops through both of them consecutively (not nested), what is the time complexity?
- A. O(n)
- B. O(A * B)
- C. O(A + B) β (correct answer)
- D. O(1)
Explanation: Because the arrays are different sizes and not nested, you add their sizes together. You cannot simplify it to O(n) unless you know A and B are the same length.
Question 25: If you loop through an array of size A, and inside that loop, you loop through another array of size B, what is the time complexity?
- A. O(A + B)
- B. O(A * B) β (correct answer)
- C. O(n^2)
- D. O(2n)
Explanation: Nested loops multiply. For every 1 element in A, the loop runs B times. Therefore, A * B total operations.
Question 26: What is the space complexity of a recursive algorithm that calls itself n times before hitting a base case, assuming no large arrays are created?
- A. O(1)
- B. O(n) β (correct answer)
- C. O(log n)
- D. O(n^2)
Explanation: Even without creating arrays, every recursive call adds a frame to the Call Stack. n calls means n frames in memory, resulting in O(n) space complexity.
Question 27: Why does doubling the size of an array in memory (resizing) occasionally cause an O(n) spike in an otherwise O(1) append() operation?
- A. Because the OS crashes
- B. Because a new, larger block of contiguous memory must be allocated, and all
n existing elements must be copied over one by one β (correct answer)
- C. Because it sorts the array
- D. Because it hashes the values
Explanation: This is why append is called *Amortized* O(1). Most of the time it's instant, but occasionally it hits the array limit and must copy n items to a new memory block.
Question 28: If a function receives an array of size n and only ever checks the first element (arr[0]), but n can be up to 1 Billion, what is the time complexity?
- A. O(n)
- B. O(1 Billion)
- C. O(1) β (correct answer)
- D. O(log n)
Explanation: The size of n doesn't matter. The algorithm only ever performs one operation (checking index 0). The runtime does not grow with the input.
Question 29: What is the time complexity of finding a specific value in a standard Binary Search Tree (BST) in the worst-case scenario (an unbalanced tree)?
- A. O(1)
- B. O(log n)
- C. O(n) β (correct answer)
- D. O(n^2)
Explanation: If a BST is unbalanced (e.g., essentially a straight line like a Linked List), you lose the "halving" benefit. You must check every node, degrading to O(n) linear time.
Question 30: What is "Amortized" Time Complexity?
- A. Time complexity calculated over a network
- B. A way of expressing the time complexity when an algorithm has very bad time complexity only once in a while, but almost always runs perfectly fast (averaging out over a sequence of operations) β (correct answer)
- C. Memory complexity
- D. Time complexity in the best case only
Explanation: Appending to a dynamic array is Amortized O(1). It's O(1) 99% of the time, and O(n) 1% of the time (during resize). On average over many operations, the O(n) penalty dilutes into O(1).