Question

Solve the recurrence to find out how many lines are printed by f(n,0), as a function of n.

Answer 1

Recurrence is used for repetitive and iterative functions

The recurrence is $T_n = O(n)$

How to determine the recurrence

The recurrence relation is defined as:

$T_n = 1 + T_{n/2} + T_{n/2}$

Rewrite the expression as:

$T_n = 1 + 2T_{n/2}$

The master theorem of recurrence states that:

$T_n = f(n) + aT_{n/b}$

By comparison, we have:

$f(n) = 1$

$a = 2$

$b = 2$

Where:

$2^k = f(n)$

So, we have:

$2^k = 1$

Express 1 as 2^0

$2^k = 2^0$

By comparison,

$k = 0$

Next, we test the relation using:

$a > b^k$

So, we have:

$a > b^0$

$a >1$

Recall that a = 2

So, we have:

$2 >1$

The above inequality is true

So, we have:

$T_n = O(n^{\log_ab})$

This gives

$T_n = O(n^{\log_22})$

Evaluate the logarithmic expression

$T_n = O(n^{1})$

$T_n = O(n)$

Hence, the recurrence is $T_n = O(n)$

Read more about recurrence at:

brainly.com/question/1275192