What is the time complexity of the following C code snippet?
Ukg technical mcq question, verified with a worked answer. Free to practise - no sign-up.
What is the time complexity of the following C code snippet?
void function(int n) {
int i = 1, s = 1;
while (s < n) {
i++;
s = s + i;
printf("Best of Luck");
}
}
Show answer & explanation
The variable 's' accumulates the sum of consecutive integers (1 + 2 + 3 + ... + k), which grows quadratically as k increases. Since the loop terminates when s reaches n, the number of iterations k is proportional to the square root of n.
Step-by-step Derivation:
Step 1: Analyze the sequence of values for 's' and 'i'.
- Initial state: i = 1, s = 1
- Iteration 1: i = 2, s = 1 + 2 = 3
- Iteration 2: i = 3, s = 3 + 3 = 6
- Iteration 3: i = 4, s = 6 + 4 = 10
- Iteration k: i = k + 1, s = 1 + 2 + 3 + ... + (k + 1)
Step 2: Express 's' as a mathematical formula after k iterations.
The sum of the first m natural numbers is given by the formula: S = m(m + 1) / 2.
In this loop, after k iterations, the value of s is the sum of integers from 1 to (k + 1).
Therefore, s = (k + 1)(k + 2) / 2.
Step 3: Determine the termination condition.
The loop terminates when s ≥ n.
(k + 1)(k + 2) / 2 ≈ n
Step 4: Solve for k in terms of n.
(k^2 + 3k + 2) / 2 ≈ n
k^2 + 3k + 2 ≈ 2n
Ignoring lower-order terms for asymptotic analysis: k^2 ≈ 2n
k ≈ sqrt(2n)
Step 5: Conclusion.
Since k is proportional to sqrt(n), the time complexity is O(sqrt(n)).