Recurrence is used for repetitive and iterative functions
The recurrence is [tex]T_n = O(n)[/tex]
The recurrence relation is defined as:
[tex]T_n = 1 + T_{n/2} + T_{n/2}[/tex]
Rewrite the expression as:
[tex]T_n = 1 + 2T_{n/2}[/tex]
The master theorem of recurrence states that:
[tex]T_n = f(n) + aT_{n/b}[/tex]
By comparison, we have:
[tex]f(n) = 1[/tex]
[tex]a = 2[/tex]
[tex]b = 2[/tex]
Where:
[tex]2^k = f(n)[/tex]
So, we have:
[tex]2^k = 1[/tex]
Express 1 as 2^0
[tex]2^k = 2^0[/tex]
By comparison,
[tex]k = 0[/tex]
Next, we test the relation using:
[tex]a > b^k[/tex]
So, we have:
[tex]a > b^0[/tex]
[tex]a >1[/tex]
Recall that a = 2
So, we have:
[tex]2 >1[/tex]
The above inequality is true
So, we have:
[tex]T_n = O(n^{\log_ab})[/tex]
This gives
[tex]T_n = O(n^{\log_22})[/tex]
Evaluate the logarithmic expression
[tex]T_n = O(n^{1})[/tex]
[tex]T_n = O(n)[/tex]
Hence, the recurrence is [tex]T_n = O(n)[/tex]
Read more about recurrence at:
https://brainly.com/question/1275192
