Big O Notation

Computer Science Master

Question 1. What does Big O notation primarily describe?

□ A. How an algorithm’s resource usage grows with input size

□ B. The exact time an algorithm will take

□ C. The number of lines of code in a program

□ D. The programming language used to write the algorithm

Question 2. Which of the following Big O complexities represents a situation where time or space usage does NOT increase with input size?

□ A. O(n) □ B. O(1) □ C. O(n^2) □ D. O(log n)

Question 3. If an algorithm takes four times as long when the input size doubles, what is its likely time complexity?

□ A. O(1) □ B. O(n) □ C. O(n^2) □ D. O(log n)

Question 4. Which example best illustrates O(log n) time complexity?

□ A. Checking each book in a pile one by one

□ B. Looking up a word in a dictionary by dividing the search space in half repeatedly

□ C. Comparing every pair of students in a class

□ D. Accessing the first element in a list

Question 5. Fill in the blank(s)

Big O notation is written as O(_______________) where the term inside the parentheses shows how resource use grows.

Question 6. Fill in the blank(s)

An algorithm with time complexity O(_) takes the same time regardless of input size.

Question 7. Fill in the blank(s)

If an algorithm has nested loops both dependent on input size, its time complexity is typically O(____).

Question 8. Fill in the blank(s)

Time complexity refers to how the algorithm's execution time changes with the size of the _______.

Question 9. Explain what O(1) time complexity means.

Question 10. Give an example of a real-world scenario that represents O(n) time complexity.

Question 11. Why is it important to consider both time and space complexity when evaluating an algorithm?

Question 12. Describe the difference between best case and worst case scenarios in algorithm complexity.

Question 13. Describe how O(n^2) time complexity grows as the input size increases, and provide a practical example to illustrate this growth.

Question 14. Explain how O(log n) algorithms maintain efficiency even as input size grows large, using the school gossip analogy.

Question 15. Discuss why understanding best, average, and worst case complexities is important when analyzing the performance of an algorithm.

Big O Notation

Answer Sheet

Question 1. What does Big O notation primarily describe?

□ A. How an algorithm’s resource usage grows with input size

B. The exact time an algorithm will take

C. The number of lines of code in a program

D. The programming language used to write the algorithm

Question 2. Which of the following Big O complexities represents a situation where time or space usage does NOT increase with input size?

A. O(n) □ B. O(1) C. O(n^2) D. O(log n)

Question 3. If an algorithm takes four times as long when the input size doubles, what is its likely time complexity?

A. O(1) B. O(n) □ C. O(n^2) D. O(log n)

Question 4. Which example best illustrates O(log n) time complexity?

A. Checking each book in a pile one by one

□ B. Looking up a word in a dictionary by dividing the search space in half repeatedly

C. Comparing every pair of students in a class

D. Accessing the first element in a list

Question 5. Fill in the blank(s)

Big O notation is written as O([[complexity]]) where the term inside the parentheses shows how resource use grows.

Question 6. Fill in the blank(s)

An algorithm with time complexity O([[1]]) takes the same time regardless of input size.

Question 7. Fill in the blank(s)

If an algorithm has nested loops both dependent on input size, its time complexity is typically O([[n^2]]).

Question 8. Fill in the blank(s)

Time complexity refers to how the algorithm's execution time changes with the size of the [[input]].

Question 9. Explain what O(1) time complexity means.

It means the time or space required by the algorithm does not increase with the size of the input; it remains constant.

Question 10. Give an example of a real-world scenario that represents O(n) time complexity.

Queuing for the school canteen where serving twice as many students takes roughly twice as much time.

Question 11. Why is it important to consider both time and space complexity when evaluating an algorithm?

Because an algorithm might be fast (low time complexity) but use a lot of memory (high space complexity), or vice versa, so both resources affect overall efficiency.

Question 12. Describe the difference between best case and worst case scenarios in algorithm complexity.

Best case is when the algorithm uses the least resources or time (optimally), while worst case is when it uses the most, representing its least efficient behavior.

Question 13. Describe how O(n^2) time complexity grows as the input size increases, and provide a practical example to illustrate this growth.

Question 14. Explain how O(log n) algorithms maintain efficiency even as input size grows large, using the school gossip analogy.

Question 15. Discuss why understanding best, average, and worst case complexities is important when analyzing the performance of an algorithm.