The

recurrence for this code is clearly T(n) = T(n – 3) + cn2 for some constant c > 0 since each
call prints out n2 asterisks and calls itself recursively on n – 3. Using the iterative method we get:
T(n) = T(n – 3) + cn2. Using the Subtraction and Conquer master theorem, we get T(n) = Θ(n3).

Problem-29  Determine Θ bounds for the recurrence relation:

Solution: Using Divide and Conquer master theorem, we get O(nlog2n).

Problem-30  Determine Θ bounds for the recurrence:

Solution: Substituting in the recurrence equation, we get:

, where k is a constant. This clearly
says Θ(n).
Problem-31  Determine Θ bounds for the recurrence relation: T(n) = T(⌈n/2⌉) + 7.
Solution: Using Master Theorem we get: Θ(logn).
Problem-32  Prove that the running time of the code below is Ω(logn).

Solution: The while loop will terminate once the value of ‘k’ is greater than or equal to the value
of ‘n’. In each iteration the value of ‘k’ is multiplied by 3. If i is the number of iterations, then ‘k’
has the value of 3i after i iterations. The loop is terminated upon reaching i iterations when 3i ≥ n
↔ i ≥ log3 n, which shows that i = Ω(logn).

Problem-33  Solve the following recurrence.

Solution: By iteration:

Note: We can use the Subtraction and Conquer master theorem for this problem.
Problem-34  Consider the following program:

Solution: The recurrence relation for the running time of this program is: T(n) = T(n – 1) + T(n –
2) + c. Note T(n) has two recurrence calls indicating a binary tree. Each step recursively calls the
program for n reduced by 1 and 2, so the depth of the recurrence tree is O(n). The number of
leaves at depth n is 2n since this is a full binary tree, and each leaf takes at least O(1)
computations for the constant factor. Running time is clearly exponential in n and it is O(2n).
Problem-35  Running time of following program?
Solution: Consider the comments in the function below:

In the above code, inner loop executes n/i times for each value of i. Its running time is
.
Problem-36  What is the complexity of
Solution: Using the logarithmic property, logxy = logx + logy, we can see that this problem is
equivalent to

This shows that the time complexity = O(nlogn).

Problem-37  What is the running time of the following recursive function (specified as a
function of the input value n)? First write the recurrence formula and then find its
complexity.

Solution: Consider the comments in the below function:

We can assume that for asymptotical analysis k = ⌈k⌉ for every integer k ≥ 1. The recurrence for
this code is . Using master theorem, we get T(n) = Θ(n).

Problem-38  What is the running time of the following recursive function (specified as a

function of the input value n)? First write a recurrence formula, and show its solution using
induction.

Solution: Consider the comments in the function below:

The if statement requires constant time [O(1)]. With the for loop, we neglect the loop overhead
and only count three times that the function is called recursively. This implies a time complexity
recurrence:

Using the Subtraction and Conquer master theorem, we get T(n) = Θ(3n).
Problem-39  Write a recursion formula for the running time T(n) of the function whose code
is below.

Solution: Consider the comments in the function below:

The recurrence for this piece of code is T(n) = T(.8n) + O(n) = T(4/5n) + O(n) =4/5 T(n) + O(n).
Applying master theorem, we get T(n) = O(n).
Problem-40  Find the complexity of the recurrence: T(n) = 2T( ) + logn
Solution: The given recurrence is not in the master theorem format. Let us try to convert this to the
master theorem format by assuming n = 2m. Applying the logarithm on both sides gives, logn =
mlogl ⇒ m = logn. Now, the given function becomes:

To make it simple we assume

.

Applying the master theorem format would result in S(m) = O(mlogm).

If we substitute m = logn back, T(n) = S(logn) = O((logn) loglogn).
Problem-41  Find the complexity of the recurrence: T(n) = T( ) + 1

Solution: Applying the logic of Problem-40 gives . Applying the master

theorem would result in S(m) = O(logm). Substituting m = logn, gives T(n) = S(logn) =
O(loglogn).
Problem-42  Find the complexity of the recurrence: T(n) = 2T( ) + 1

Solution: Applying the logic of Problem-40 gives: . Using the master

theorem results S(m) = . Substituting m = logn gives T(n) =O(logn).
Problem-43  Find the complexity of the below function.

Solution: Consider the comments in the function below:

For the above code, the recurrence function can be given as: T(n) = T( ) + 1. This is same as
that of Problem-41.
Problem-44  Analyze the running time of the following recursive pseudo-code as a function of
n.

Solution: Consider the comments in below pseudo-code and call running time of function(n) as
T(n).
T(n) can be defined as follows:

Using the master theorem gives: .

Problem-45  Find the complexity of the below pseudocode:

Solution: Consider the comments in the pseudocode below:

The recurrence for this function is T(n) = T(n/2) + n. Using master theorem, we get T(n) = O(n).
Problem-46  Running time of the following program?

Solution: Consider the comments in the below function:

Complexity of above program is: O(nlogn).

Problem-47  Running time of the following program?

Solution: Consider the comments in the below function:

The time complexity of this program is: O(n2).

Problem-48  Find the complexity of the below function:
Solution: Consider the comments in the below function:

The recurrence for this function is: . Using master theorem, we get T(n) =
O(n).
Problem-49  Find the complexity of the below function:
Solution:

Time Complexity: O(logn * logn) = O(log2n).

Problem-50  ∑i≤k≤n O(n), where O(n) stands for order n is:
(A) O(n)
(B) O(n2)
(C) O(n3)
(D) O(3n2)
(E) O(1.5n2)

Solution: (B). ∑i≤k≤n O(n) = O(n) ∑i≤k≤n 1 = O(n2).

Problem-51  Which of the following three claims are correct?

I (n + k)m = Θ(nm), where k and m are constants
II 2n+1 = O(2n)
III 22n+1 = O(2n)
(A) I and II
(B) I and III
(C) II and III
(D) I, II and III

Solution: (A). (I) (n + k)m =nh + c1*nk–1 + ... km = Θ(nh) and (II) 2n+1 = 2*2n = O(2n)
Problem-52  Consider the following functions:
f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is
true?
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = Ω (g(n)); g(n) = O(h(n))