Question

A loop within a loop will have the time complexity as ________.

• A. \(n^2\)
• B. \(\log(n)\)
• C. \(n\)
• D. \(n^3\)

Hint:

Single loop of size \(n \rightarrow O(n)\).
Two nested loops of size \(n \rightarrow O(n^2)\).
Three nested loops of size \(n \rightarrow O(n^3)\).

Answer 1

The Correct Option is A

Concept:
Time complexity characterizes the growth rate of an algorithm's running time relative to the input size \(n\).
When control structures such as loops are nested, their iteration counts multiply.

Step 1: Analyzing Nested Loops:
Consider a standard nested loop structure where an outer loop runs from \(1\) to \(n\):
For each iteration of the outer loop, an inner loop runs from \(1\) to \(n\).
The outer loop executes \(n\) times.
For every single execution of the outer loop, the inner loop executes \(n\) times.

Step 2: Calculating Total Iterations:
The total number of operations executed by the inner body is given by: \[ \text{Total operations} = n \times n = n^2 \] Expressed in Big-O notation, the asymptotic time complexity is quadratic: \[ O(n^2) \] This is the characteristic complexity seen in nested loops found in algorithms such as Bubble Sort and Selection Sort.
Final Answer:
A loop nested within another loop over the same input size yields a complexity of \(n^2\). Therefore, option (A) is correct.