Question

How many lines, as a function of n (in $\mathbf{⊝}(.)$form), does the following program print? Write a recurrence and solve it. You may assume is a power of . function f (n) if n > 1:

print_line (‘‘still going’’)

f (n/2)

f (n/2)

Short answer

The number of lines will be: $⊝\left(n\right)$

Step-by-step solution

Creating Recurrence Relation

If indeed the data size n is bigger than 1 , the supplied function f(n) displays one line "still continuing" and executes the function f(n) recursively by passing the input of half the size.

That is, each call divides the issue into two half-sized sub-problems. In addition, the function displays the line in a fixed time for each call.

As a result, a recurrence relation for the number of lines printed by the provided function may be established as follows:

$\mathrm{T}\left(\mathrm{n}\right)=2\mathrm{T}\left(\mathrm{n}/2\right)+0\left(1\right)$ …… (1)

Here, $\mathrm{T}\left(1\right)=0\mathrm{and}\mathrm{T}\left(2\right)=1$

Solving Recurrence Relation

• This stored procedure recursive calls produce a recursion tree structure. Because the issue divides into two subtasks of half original size in each recursive iteration, there are two sub-problems at each level of the tree.

• Assume$\mathrm{n}=2^{\mathrm{k}}$. That really is, n is a two-digit power. As a result, the recursion finishes at the k th level, as well as the sub-problems' input sizes are reduced to size1 . The supplied method does not display the lines when the input size is 1 .

• As a result, only the lines from level to level are printed $\left(\mathrm{k}-1\right)$.

• Since, each $2^i$sub problem prints the line only once and there are sub problems at level $2^i$, the number of times the line is printed at level $\mathrm{i}=2^{\mathrm{i}}$.

• Add up the total number of characters printed on each level.

As a result, the overall amount of times each line is printed is calculated.

$$\begin{gathered} =1+2^1+2^2+...+2^{k-1} \\ =\frac{\left(1\right)\left(2^k-1\right)}{2^k-1} \\ =n-1 \end{gathered}$$

Thus, $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{n}-1$

Then, for some constant c>0 ,

$$\begin{gathered} T\left(n\right)=n-1 \\ \le c.n \\ =0\left(n\right) \end{gathered}$$

Also, for some constant $c>0$,

$$\begin{gathered} \mathrm{T}\left(\mathrm{n}\right)=\mathrm{n}-1 \\ \ge \mathrm{c}.\mathrm{n} \\ =\mathrm{\Omega }\left(\mathrm{n}\right) \end{gathered}$$

Thus, role="math" localid="1658921049129" $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{\Theta }\left(\mathrm{n}\right)$.

As a result, the software prints a certain amount of lines $\mathrm{\Theta }\left(\mathrm{n}\right)$.

To use the Master’s theorem to solve the recurrence:

To solve the recurrence relation, apply the master theorem (1). Compare and contrast the recurrence relation (1) with both the formula (2).

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{aT}\left(\mathrm{n}/\mathrm{b}\right)+\mathrm{O}\left({\mathrm{n}}^{\mathrm{d}}\right)$ …… (2)

Then, a=2,b=2 and d=0

Compare d and ${\log }_{b}a$

Where ${\log }_{b}a={\log }_{2}2=1andd=0$.

Since $d<{\log }_{b}a$, by the third case of master theorem,

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{logb}\mathrm{a}}\right)=\mathrm{\Theta }\left(\mathrm{n}\right)$

Therefore, the number of lines printed by the program is $\mathrm{\Theta }\left(\mathrm{n}\right)$ .