Awesome q2a theme
+1 vote
85 views

  • 🚩 Duplicate | 👮 Hira Thakur | 💬 “already present in GO.”
in Programming by (181 points) 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

@goxul @Pratyush Priyam Kuan

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.

1 Answer

0 votes
200 definitely
by (17 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jul 2020
  1. Shaik Masthan

    39 Points

  2. hiteshpujari

    9 Points

  3. Venkatesh Akhouri

    6 Points

  4. Meghana518

    6 Points

  5. bittujash

    6 Points

  6. Pawan_k

    6 Points

  7. rits78671

    6 Points

  8. srestha

    6 Points

  9. RavGopal

    4 Points

  10. Sumaiyas

    4 Points

7,543 questions
1,783 answers
10,867 comments
90,482 users