MadeEasy Test Series: Algorithms - Time Complexity

Question

Consider you are playing game of shooting balloon and you are expected to shoot n balloons in the board. If you are a sharp shooter(100% accuracy) and for every two balloons you are able to shoot, one new balloon is inserted into the board, then what is the time complexity of this shooting procedure if the board has to be emptied?

(a) O(1)

(b) O(n)

(c) O(logn)

(d) O(n2)

Comments

Answer should be " B" - O(n)

Answer 1

O(2n) = O(n).

option B should be the answer

Comments

can you please elaborate how you solved this?

---

Every after 2 shots u have reduced the number of birds by 1. Thus, u will take time t = twice the number of birds to empty them. This is simply a linear solution in time domain.

Anyways in which test series this question was asked??

---

got it..thanks :)

it was asked in made easy test series

---

By completing n baloons, there are $\frac{n}{2}$ new baloons..

By completing $\frac{n}{2}$ baloons, there are again $\frac{n}{4}$ new baloons..

By completing $\frac{n}{4}$ baloons, there are again $\frac{n}{8}$ new baloons..  goes on to 1 then 0

let 2^k = n.

∴ n + $\frac{n}{2}$ + $\frac{n}{4}$ + ..... + 1 = n $(\; 1 + \frac{1}{2}$ + $\frac{1}{4}$ +  $\frac{1}{8}$ + $\frac{1}{16}$ + ... $\frac{1}{2^{k-1}}$ + $\frac{1}{2^{k}} \;)$

= $\frac{n}{2^{k}}$ ( 2^k + 2^k-1 + 2^k-2 +..... + 2⁰ ) = ( 2^k + 2^k-1 + 2^k-2 +.....+ 2⁰ ) = 2^k+1 - 1 = 2n - 1 = O(n)