Time and Space Complexity : MCQs & PYQs with Explanation

Option D

The growth of functions is compared using time complexity. As input size n increases, different functions grow at different rates. The general order of growth from lower to higher is O(n log n)<O(n²)<O(n³)<O(2ⁿ).
Exponential functions like 2n grow much faster than polynomial functions such as n2 or n3.
For example, if n is 10:

• n²=100
• n³=1000
• 2ⁿ=1024

As n increases further, the gap becomes even larger.

Option A

Algorithm Complexity represents how the running time or space requirement of an algorithm increases as the input size n increases. 
In ascending order, complexities are arranged from fastest growth efficiency to slowest efficiency (smallest growth to largest growth).

• O(log₂n) grows very slowly and is considered highly efficient.
• O(n) grows linearly with input size.
• O(nlog₂n) grows slightly faster than linear complexity.
• O(n²) is quadratic complexity and grows much faster.
• O(2ⁿ) is exponential complexity and grows extremely fast.

Therefore, the correct ascending order is O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(2ⁿ).
The term log₂n means “How many times can we divide n by 2 until we reach 1?”. It is called logarithm with base 2. Mathematically, log₂n=x. Means 2^x=n.

Common Time Complexities:

Option B

The time complexity of converting an infix expression to a postfix expression is O(N). This is because the algorithm scans the infix expression one character at a time from left to right.
For each character (operands, operators, parentheses), the algorithm may push it onto a stack or pop it from the stack. Each element is pushed and popped at most once, so the total number of operations grows directly with the length of the expression.
Since no nested loops or repeated scans are used, the overall work done is proportional to N, where N is the number of characters in the expression. Therefore, the time complexity is O(N).

Option D

Asymptotic Notation is used to measure how the running time of an algorithm grows as the input size increases. It does not count exact time, but shows the behavior of the algorithm for large inputs.
Big-O Notation (O):
Big-O tells us the worst-case performance of an algorithm. It means the maximum time an algorithm may take in the worst situation. Big-O answers the question: “What is the slowest this algorithm can be?”
Omega Notation (Ω):
Omega represents the best-case performance of an algorithm. It shows the minimum time required when the input is in the most favorable condition. Omega answers the question: “What is the fastest this algorithm can be?”
Theta Notation (Θ):
Theta gives the average or exact growth rate of an algorithm. It is used when the best case and worst case grow at the same rate. Theta answers the question : “On average, how does this algorithm perform?”
E.g.: 
If searching for an element in a list:

• Best case (Ω): Element found at first position.
• Worst case (O): Element found at last position or not found.
• Average case (Θ): Element found somewhere in the middle.

In short:

• Big-O : Worst Case / Upper Bound.
• Omega (Ω) : Best Case / Lower Bound.
• Theta (Θ) : Average Case / Tight Bound.

Option B

Option D

When a code contains n nested loops, and each loop runs from 1 to m, the inner loop executes m times for every iteration of the outer loop.
For two nested loops running from 1 to m time complexity will be m² . Similarly, for n nested loops running from 1 to m time complexity will be mⁿ.

• O(n+m) applies to sequential loops.
• O(n*m) applies when there are two loops where one depends on n and the other on m.