Register

Recurrence

337 views
3 votes
3 votes
Solve the Recurrence

$$\begin{align} T(n) &= T \left ( \frac n 2 -1 \right ) + T \left ( n- \frac n 2 \right ) + \Theta(n) \end{align}$$
User Avatar

1 Answer

Best answer
11 votes
11 votes

In recurrence relation , floor , ceil , addition of constant terms etc are not required for solving as we need asymptotic solution..So

       T(n)  = T(n/2 - 1)  + T(n - n/2) + θ(n)

==> T(n)  = T(n/2)  + T(n/2)  + θ(n)

==> T(n)  = 2T(n/2)  + θ(n)

==> T(n)  =  θ(nlogn)    [Using 3rd case of Master's Theorem]

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
jenilS7 asked Mar 18
126 views
Recurrence relation
What is the returned value by the given function below. Algo fun(n) { If(x<=2) return 1; Else { Return fun(n1/2) + n; } } Note : Assume that all the syntax and data type constraints are valid and just check algorithm.
What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + n; }}Note : Assume that all...
User Avatar
0 votes
0 votes
1 answer
2
vivek1211 asked Oct 2, 2023
260 views
solve this recurrence relation
T(n) = T(n^1/2) + n doing this in substitution method gives the ans as O(n) but using tree recursion gives the ans as O(nlogn) which of these are correct and which has to be considered for worst case
T(n) = T(n^1/2) + ndoing this in substitution method gives the ans as O(n)but using tree recursion gives the ans as O(nlogn)which of these are correct and which has to be...
User Avatar
0 votes
0 votes
1 answer
3
practicalmetal asked Sep 15, 2023
381 views
Recurrence relations
Consider the following function: function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); } Find the worst case time complexity of function X ?
Consider the following function:function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); }Find the worst case time complexity of function...
User Avatar
0 votes
0 votes
0 answers
4
rexritz asked Aug 13, 2023
301 views
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
Link Copied!