The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
50 views

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


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

28,834 questions
36,688 answers
90,625 comments
34,641 users