edited by
1,828 views
2 votes
2 votes

The solution of the reccurence relation

$T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+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
edited by

2 Answers

1 votes
1 votes

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)

Answer:

Related questions

3 votes
3 votes
1 answer
2
2 votes
2 votes
1 answer
3
go_editor asked Aug 9, 2016
4,294 views
If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in$O(d \: n \: k)$$O(d n^k)$...