retagged by
795 views
0 votes
0 votes

​​​​​​Solve the following recursions ( in terms of Θ ).

T(0) = T(1) = Θ(1) in all of the following.

  1. $T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n-1}T(i)$
  2. $T(n) = n + \frac{2}{n}\sum_{i=0}^{i=n-1}T(i)$
  3. $T(n) = n + \frac{4}{n}\sum_{i=0}^{i=n/2}T(i)$
  4. $T(n) = n + \frac{40}{n}\sum_{i=0}^{i=n/5}T(i)$
retagged by

1 Answer

4 votes
4 votes

 

You can solve the first and second problem using this method.

Related questions

1 votes
1 votes
1 answer
1
Shaik Masthan asked Aug 27, 2019
1,014 views
Given an array of ( both positive and negative ) integers, $a_0,a_1,….a_{n-1}$ and $l, 1<l<n$.Design a linear time algorithm to compute the maximum product subarray, wh...