Made easy test series

Question

Answer 1

Following will be the equation for the given code snippet-:

    $n+\frac{n}{2}+\frac{n}{2^{2}}+\frac{n}{2^{3}}+...1$

$=n+\frac{n}{2}+\frac{n}{2^{2}}+\frac{n}{2^{3}}+...\frac{n}{2^{k}}$$\therefore 2^k=n$

$=n(\frac{1}{2^{0}}+\frac{1}{2^{1}}+\frac{1}{2^{2}}+\frac{1}{2^{3}}+...\frac{1}{2^{k}})$

=$n \times \frac{1-(\frac{1}{2})^{k}}{1-\frac{1}{2}}=2n -\frac{n}{2^k}=2n-1$

Comments

I hope the series should starts with n right?

---

yes you are right!

thanks

---

check the summation of GP formula... there are totally n+1 terms in the series

Answer 2

The number of times 'j' value will be incremented is dependent on 'i' value and here 'i' value is being halved every time so,

T(n)= $n$ + $\frac{n}{2}$ + $\frac{n}{4}$ + $\frac{n}{8}$ +.......+ $1$

= n [$1$ + $\frac{1}{2}$ + $\frac{1}{4}$ + $\frac{1}{8}$ +.......+$\frac{1}{n}$]

=n × O(1)

=O(n)

Comments

What's the difference between the above two series ? Both are same. After evaluating each separately  logn will come.

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

---

@ Kajal Khobragade how can 

$n + \frac{n}{2} + \frac{n}{4} +...+ 1 =O(nlogn)$ ? 

see my answer

---

ohh i got my mistake :(

thanks:)