+1 vote
85 views

• 🚩 Duplicate | | 💬 “already present in GO.”
1 flag | 85 views
0
What part of the given solution did you not understand?
0
What is the time complexity you are getting?
0
200?
0
The answer is given as O(n^2).
+1
$1*(\frac{n}{2}+\log_{2} n) + 2*(\frac{n}{2}+\log_{2} n) + 4*(\frac{n}{2}+\log_{2} n) + 8*(\frac{n}{2}+\log_{2} n) + ... + 2^{k}*(\frac{n}{2}+\log_{2} n)$

$2^k = n \Rightarrow k = \log_{2} n$

$Using \ the \ GP \ formula$

$(\frac{n}{2}+\log_{2} n) *\left \lbrace 1 + 2 + 4 +8 +16 + ... 2^k \right \rbrace$

$\Rightarrow \ (\frac{n}{2}+\log_{2} n)* \left \lbrace 2^{\log_{2} n+1}-1 \right \rbrace$

$\Rightarrow \ (\frac{n}{2}+\log_{2} n)* \left \lbrace n\right \rbrace$

$\Rightarrow O(n^2)$
0
Yes!
0

doesn't the outer loop run $\log_2n$ times ?

Then it'll be $(\frac{n}{2}+\log_{2} n)*(\log_{2} n)$ right ?

0

@pranay562 Outer loop does run for log n times but the 2nd loop will run log i times for each iteration where i = 2,4,8,16,..... . so,we need to find the total iterations to find the time complexity.