The Gateway to Computer Science Excellence
+2 votes
775 views

The solution of the reccurence relation

$T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T(\frac{n}{s})+T(\frac{7n}{10}+6)+O(n) & \text{ if } n> 80 \end{cases}$ is

  1. O(lg n)
  2. O(n)
  3. O(n lg n)
  4. None of the above
in Algorithms by Veteran
recategorized | 775 views

1 Answer

+1 vote

Assuming that s is a constant or 5 is misprinted as s:

Given question can be reduced as:

T(n) = T([n/s] ) + T(7n/10 + 6) + O(n)
≤ c[n/s] + c(7n/10 + 6) + O(n)
≤ c((n/s)  + 7cn/10 + 6c + O(n)
≤  cn

We can say T(n

T(n) =O(n)

by Boss
0
bro ,how can i learn abt Recurrence relations,plz suggest sm books or online material -thanku

Related questions

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
52,218 questions
59,891 answers
201,086 comments
118,128 users