test-series

Question

What is the time complexity of the following code snippet? Assume x is a global variable and “statement” takes O(n) time?

Comments

I think it should be O(logn)

---

but answer is 0(n).

---

please explain...

---

I think they arr taking RR is T(n) = T(n/2) + n.

TC = O(n).

But "statement" will always take O(n) because they did not explicitly mention the relation between T(n) and (n). so for every T(n/2^k) it will take (n) for all k = 1 to k. and k will go up to logn. Hence its TC should be O(nogn).

Answer 1

Time complexity will depend on statement.