The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
709 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 (103k points)
recategorized | 709 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 (32.2k points)
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
50,362 questions
55,788 answers
192,413 comments
90,925 users