What will be the time complexity of the func() function in the following code?…
2024
What will be the time complexity of the func() function in the following code?
using namespace std;
void func(int a[], int n, int k)
{
if (k <= n)
{
for (int i = 0; i < k/2; i++)
swap(a[i], a[k-i-1]);
}
}
int main()
{
int a[] = {1, 2, 3, 4, 5};
int n = sizeof(a) / sizeof(int), k = 3;
func(a, n, k);
for (int i = 0; i < n; ++i)
cout << a[i]<<" ";
return 0;
}
Answer: A. O(k) — The time complexity of a block of code depends only on the loop(s) or recursive calls that actually execute, counted as a function of whichever variable…
- A.
O(k)
- B.
O(n)
- C.
O(k log k)
- D.
O(n log n)
Attempted by 128 students.
Show answer & explanation
Correct answer: A
The time complexity of a block of code depends only on the loop(s) or recursive calls that actually execute, counted as a function of whichever variable bounds their iteration count. A guard condition that is checked once, and any routine that is not part of the algorithm being analysed -- such as input initialisation or result display -- do not affect this growth rate.
The guard if (k <= n) is checked once: with k = 3 and n = 5, 3 <= 5 is true, so the block executes -- this check is a single constant-time comparison.
The loop bound is k/2. With k = 3, integer division gives k/2 = 1, so the loop runs for exactly i = 0 -- one iteration.
Each iteration performs one constant-time swap: swap(a[i], a[k-i-1]), e.g. swap(a[0], a[2]).
So the total work inside func is (number of iterations) x (constant work per iteration) = O(k/2) = O(k) -- it depends only on k, never on n.
Back in main, the separate loop for (int i = 0; i < n; ++i) cout << a[i]; belongs to main, not to func -- it only displays the array after func has returned, and is outside the scope of func's complexity that the question asks for.
Cross-check: holding k fixed and increasing n changes nothing about the number of swaps performed, while increasing k (with n large enough) increases the swap count proportionally -- confirming the growth rate tracks k, not n. There is also no nested loop, recursion, or comparison-based sorting step that could introduce a logarithmic factor, ruling out O(k log k) and O(n log n).
So the time complexity of func -- the routine that reverses the first k elements of the array -- is O(k).