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

asked in Algorithms by Veteran (44.1k 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.7k points)  
selected by

Related questions

0 votes
0 answers
1
asked in Algorithms by NIHAR MUKHIYA (47 points)   | 36 views
0 votes
0 answers
2
asked in Algorithms by Meenakshi Sharma Loyal (3.8k points)   | 21 views


Top Users Jul 2017
  1. Bikram

    4062 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1658 Points

  5. Arjun

    1294 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1054 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    706 Points


24,022 questions
30,966 answers
70,346 comments
29,342 users