ME Testseries

Question

What is the time complexity of the following program?

Answer 1

O(n) because:

The  count function will get executed like as follows:

for i=n --->    count will execute n times

for i=n/2---->   count will get executed n/2 times

.

.

.

.for i=1-->  count will get executed for 1 time

 

so, we will sum up all of this:

O(n+n/2+n/4+.......1)=O(n)

Comments

@Magma

let n = $2^{k}$, another way of writing it is like,

$2^{0}+2^{1}+2^{2}+2^{3}+.......+2^{k-2}+2^{k-1}+2^{k}$ ==> which is a GP series, evaluate it !

---

Nice approach

---

the above gp will give:

when k-->infinity

sum=a/r-1=1/0.5=2

so, O(2n) i.e. O(n)