GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
50 views

asked in Algorithms by Veteran (45.2k points)   | 50 views
whats the answer?Is it O(n log N) ?? I am trying by substitution.

1 Answer

+2 votes
Best answer

t(n)=√nt(√n)+n
using recurence tree method
every time our main problem goes decreases to n->n1/2->n1/4......n1/2^k
nd cost of reduction for size k is √k where k is a function of n 
so after how much time our subproblem becom of size 1 0r 2 i mean when cost becomes constant
.n1/2^k=2  k=loglogn
here cost at each level is same at each level bcoz our main problem is uniformally divided =n
so  total cost using recurence tree method =
    no of levels*cost at each level = loglogn * n=nloglogn
Ans=θ(nloglogn)

answered by Veteran (10.9k points)  
selected by

Related questions

0 votes
1 answer
1
0 votes
1 answer
2
+1 vote
1 answer
3
asked in Algorithms by kallu singh Junior (657 points)   | 35 views


Top Users Sep 2017
  1. Habibkhan

    8796 Points

  2. rishu_darkshadow

    3544 Points

  3. Warrior

    2914 Points

  4. Arjun

    2840 Points

  5. A_i_$_h

    2550 Points

  6. manu00x

    2268 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points


26,346 questions
33,924 answers
80,521 comments
31,230 users