Q.1 What does 'time complexity' of an algorithm measure?
The amount of memory used by the algorithm
The time taken by the algorithm as a function of input size
The number of lines of code in the algorithm
The number of programmers required
Explanation - Time complexity represents how the execution time of an algorithm changes with the input size.
Correct answer is: The time taken by the algorithm as a function of input size
Q.2 What is 'space complexity'?
The physical space an algorithm occupies on disk
The amount of memory required by an algorithm
The number of variables used in an algorithm
The number of functions in an algorithm
Explanation - Space complexity measures the memory usage of an algorithm with respect to input size.
Correct answer is: The amount of memory required by an algorithm
Q.3 If an algorithm has O(n) time complexity, what does it imply?
Execution time increases linearly with input size
Execution time is constant regardless of input size
Execution time increases quadratically with input size
Execution time decreases with input size
Explanation - O(n) means the running time grows proportionally to the input size.
Correct answer is: Execution time increases linearly with input size
Q.4 Which of the following represents the best case time complexity of an algorithm?
The shortest time the algorithm takes for a given input
The longest time the algorithm takes for a given input
Average time for all inputs
Time required to compile the algorithm
Explanation - Best case refers to the scenario where the algorithm performs the minimum number of steps.
Correct answer is: The shortest time the algorithm takes for a given input
Q.5 What does O(1) time complexity mean?
Time increases with input size
Time decreases with input size
Time is constant regardless of input size
Time increases logarithmically
Explanation - O(1) indicates the algorithm takes the same amount of time no matter the input size.
Correct answer is: Time is constant regardless of input size
Q.6 Which of the following complexities is better for large inputs?
O(n^2)
O(n log n)
O(2^n)
O(n!)
Explanation - O(n log n) grows slower than O(n^2), O(2^n), and O(n!) for large inputs, making it more efficient.
Correct answer is: O(n log n)
Q.7 What is the worst case time complexity of linear search in an unsorted array?
O(1)
O(n)
O(log n)
O(n^2)
Explanation - In the worst case, linear search examines each element once, resulting in O(n) complexity.
Correct answer is: O(n)
Q.8 Which complexity notation gives an upper bound of an algorithm's growth rate?
Big O (O)
Big Omega (Ω)
Big Theta (Θ)
Little o (o)
Explanation - Big O notation provides an upper bound on the growth rate, representing worst-case performance.
Correct answer is: Big O (O)
Q.9 The average case complexity gives:
Time taken in the best scenario
Time taken in the worst scenario
Expected time over all possible inputs
Time taken for inputs of size 1
Explanation - Average case complexity represents the expected running time for all possible inputs of a given size.
Correct answer is: Expected time over all possible inputs
Q.10 What is the space complexity of a recursive function with n recursive calls?
O(1)
O(n)
O(log n)
O(n^2)
Explanation - Each recursive call adds a frame to the call stack, so n calls require O(n) space.
Correct answer is: O(n)
Q.11 If an algorithm requires 2^n steps, its time complexity is:
O(n^2)
O(log n)
O(n)
O(2^n)
Explanation - The number of steps doubles with each additional input, characteristic of exponential complexity.
Correct answer is: O(2^n)
Q.12 What is the time complexity of binary search on a sorted array?
O(n)
O(log n)
O(n log n)
O(n^2)
Explanation - Binary search repeatedly divides the search interval in half, giving logarithmic time complexity.
Correct answer is: O(log n)
Q.13 Which of the following is NOT a factor affecting time complexity?
Input size
Number of operations
Memory allocation
Algorithm design
Explanation - Memory allocation affects space complexity, not directly time complexity.
Correct answer is: Memory allocation
Q.14 An algorithm with O(n!) complexity is usually:
Very fast
Efficient for large n
Extremely slow for large n
Independent of input size
Explanation - Factorial complexity grows extremely fast with input size, making it impractical for large n.
Correct answer is: Extremely slow for large n
Q.15 Which of the following best describes logarithmic complexity?
Time doubles with each additional input
Time halves with each additional input
Time grows very slowly even for large inputs
Time grows quadratically
Explanation - Logarithmic complexity grows slowly compared to linear or quadratic complexities.
Correct answer is: Time grows very slowly even for large inputs
Q.16 What is the space complexity of iterative algorithms that do not use extra data structures?
O(n)
O(1)
O(log n)
O(n^2)
Explanation - Iterative algorithms with no extra storage use constant space regardless of input size.
Correct answer is: O(1)
Q.17 Which complexity is better for real-time systems?
O(n!)
O(2^n)
O(n^2)
O(1)
Explanation - Constant-time algorithms are predictable and suitable for real-time systems.
Correct answer is: O(1)
Q.18 Which notation gives both upper and lower bounds on complexity?
Big O (O)
Big Omega (Ω)
Big Theta (Θ)
Little o (o)
Explanation - Θ notation tightly bounds the algorithm's growth from above and below.
Correct answer is: Big Theta (Θ)
Q.19 The best case time complexity of linear search is:
O(n)
O(log n)
O(1)
O(n^2)
Explanation - If the element is the first one, linear search finds it in constant time.
Correct answer is: O(1)
Q.20 Which of the following affects space complexity?
Input size
Number of variables
Recursion depth
All of the above
Explanation - Space complexity depends on input size, number of variables, and recursive stack usage.
Correct answer is: All of the above