Question: Solve the following recurrence relations and give a bound for each of them.

(a)T(n)=2T(n/3)+1(b)T(n)=5T(n/4)+n(c)T(n)=7T(n/7)+n(d)T(n)=9T(n/3)+n2(e)T(n)=8T(n/2)+n3(f)T(n)=49T(n/25)+n(3/2)logn(g)T(n)=T(n-1)+2(h)T(n)=T(n-1)+nc,whereisaconstant(i)T(n)=T(n-1)+cn,whereissomeconstant(j)T(n)=2T(n-1)+1(k)T(n)=T(n)+1

Short Answer

Expert verified

θbound for each recurrence relation is as follows:

aO(nlog32)bO(nlog45cO(nlogn)dO(n2logn)eO(n2logn)dO(n32logn)eO(n)fO(nc+1)gO(cn)hO(2n)iO(log(logn))

Step by step solution

01

Introduction

In above question there will be total a to k different formula theorem. Which we have to make it correct as per the calculation process is given and on that base we have to write answer base on the calculation of program is written during calculation.

To see all the calculation with given formulation check step-2 as below.

02

Calculation of  Θ bound

O(loglogn)T(n-2)(a)

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

Evaluate the two recurrence equation's master theorem.

localid="1658923707909" T(n)=aT(n/b)+nc ---(2)

By simply compare & calculate equation (1) and (2), the value of

nCis1,cis0,bis3&ais2.

By master’s theorem, if the value of then the running time is,

T(n)=Onlogba ---(3)

Here, the value of logba=log32=063092and it is greater than “c”.

Substitute the values of “b” as 3 and “a” as 2 in equation (3). So the running time of algorithm is,

localid="1658923595278" T(n)=Onlog32

Therefore, the algorithm takes a run time of: localid="1658924131831" Onlog32.

(b)

T(n)=5T(n/4)+n ---(1)

Consider the master theorem for the following recurrence equation,

T(n)=aT(n/b)+nc ---(2)

By equality of calculation of equation (1) and (2), the value of ncisnn,cis1,bis4andaais5.

By main theorem, if the value of c<logba, running time is,

localid="1658924099025" T(n)=Onlogba ---(3)

Here, the number of logba=log45=1.160963and it’s bigger than “ c ”.

Extra/substitute the detail of “ b ” as 4 and “ a ” as 5 in equation (3). Thus, time is going for algorithm,

localid="1658924202541" T(n)=Onlog54

As a result, the method requires a run time of localid="1658924182217" Onlog45.

(c)

T(n)=7T(n/7)+n

Check out the following recurrence equation's governing theorem:

T(n)=aT(n/b)+nc ----- (2)

The amount of may be determined by comparing equations (1) and (2). ncisn,cis1,bis7andais7.

By master’s theorem, if the value of c=logba,,then the running time is,

T(n)=O(nclogn) ---(3)

Here, the value of and it is equal to “ ”.

Substitute the value of “c ” as in equation (3). So the running time of algorithm is,

T(n)=(n3logn)O(nlogn)

Therefore, the algorithm takes a run time of O(nlogn).

(d)

The recurrence relation is shown below:

T(n)=9T(n/3)+n2 ----(1).

Check out the following recurrence equation's governing theorem,

T(n)=aT(n/b)+n2 ----(2)

By equally manage equation with calculation of (1) and (2), the value of ncisn2,cis2,bis3andais9.

By main theorem, if the amount of , then the time is going,

T(n)=O(nclogn) ----(3)

Here, the value of logba=log39=2 and it is equal to “ c ”.

In the equation, replace "c " with " 2 " (3). As a result, the algorithm's execution time is

T(n)=O(n2logn)

Therefore, the algorithm takes a run time of O(n2logn)..

(e)

The recurrence relation is shown below:

T(n)=8T(n/2)+n3 ----(1)

Consider the following recurrence equation's master theorem

T(n)=aT(n/b)+n2 ----(2)

The value of may be determined by comparing equations (1) and (2) .

ncis,cis3,bis2andais8.

According to the master's theorem, if the value of c=logba, then the running time is,

T(n)=O(nclogn) ----(3)

Here, the value logba=logb8=3of and it is equal to “c ”.

In equation, change the value of "c " to 3. (3). As a result, the algorithm's execution time is

T(n)=O(n3logn)

Therefore, the algorithm takes a run time of .

(f)

The recurrence relation is shown below:

localid="1658980924866" T(n)=49(n/25)+n32logn ----(1)

Consider the master theorem for the following recurrence equation,

T(n)=aT(n/b)+n2 ----(2)

By comparing equation (1) and (2), the value of ncisn32logn,cislogn=1.5logn,bis25andais.

By master’s theorem, if the value of c>logba,, then the running time is,

T(n)=O(nc) ----(3)

The value of logba=log2549=1.209062 is less than the value of “c ” is 1.5logn..

Substitute the value of “c ” as 32logn in equation (3). So the running time of algorithm is localid="1658981448371" T(n)=O(n32logn).

Therefore, the algorithm takes a run time of O(n32logn)

(g)

T(n)=T(n-1)+2........(1)T(n-1)canberepresentedasfollows:T(n-1)=T((n-1)-1)+2=T(n-2)+2.......(2)T(n-2)canberepresentedasfollows:T(n-2)=T((n-2)-1)+2=T(n-3)+2.......(3)T(n-3)canberepresentedasfollows:T(n-3)=T((n-3)-1)+2=T(n-4)+2..........(4)

Substitute equation (2) in equation (1). Hence, can be rewritten as follows:

T(n)=T(n-2)+2+2=T(n-2)+4

----(5)

Substitute equation (3) in equation (5).

T(n)=T(n-3)+2+4=T(n-3)+6 ----(6)

Substitute equation (4) in equation (6).

T(n)=T(n-4)+2+6=T(n-4)+8 ----(7)

In general, can be written as follow:

T(n)=T(n-k)+kc ----(8)

Substitute the value of then equation (8) can be represented as follows:

T(n)=T(0)+nc ----(9)

Let T(0)=1. Thus, the running of (n) depends only on the value of “ n ” which is as follows:

T(n)=1+nc=O(n)Therefore,T(n)=O(n)

(h)

T(n)=T(n-1)+nc............(1)T(n-1)canberepresentedasfollows:T(n-1)=T((n-1)-1)+nc=T(n-2)+nc.......(2

T(n-2)can be represented as follows:

T(n-2)=T((n-2)-1)+nc=T(n-3)+nc ----(3)

T(n-3) can be represented as follows:

T(n-3)=T((n-3)-1)+nc=T(n-4)+nc ----(4)

Substitute equation (2) in equation (1). Hence, T(n) can be rewritten as follows:

T(n)=T(n-2)+nc+nc=T(n-2)+2nc ----(5)

Substitute equation (3) in equation (5)

T(n)=T(n-3)+nc+2nc=T(n-3)+3nc ----(6)

Substitute equation (4) in equation (6).

T(n)=T(n-4)+nc+3nc=T(n-4)+4nc ----(7)

In general, T(n) can be written as follow:

T(n)=T(n-k)+knc ----(8)

Substitute k=n then equation (8) can be represented as follows:

T(n)=T(n-n)+n.nc=T(0)+n(c+1) ----(9)

Let T(0)=1. Thus, the running of T(n) depends only on the value of “n ” which is as follows:

T(n)=1+(nc+1)=O(nc+1)Therefore,T(n)=O(nc+1)

(i)

T(n)=T(n-1)+cn ----(1)

T(n-1) can be represented as follows:

T(n-1)=T((n-1)-1)+cn=T(n-2)+cn

----(2)

T(n-2) can be represented as follows:

T(n-2)=T((n-2)-1)+cn=T(n-3)+cn

----(3)

T(n-3) can be represented as follows:

T(n-3)=T((n-3)-1)+cn=T(n-4)+cn

----(4)

Substitute equation (2) in equation (1). Hence,T(n) can be rewritten as follows:

T(n)=T(n-2)+cn+cn=T(n-2)+2cn ----(5)

Substitute equation (3) in equation (5).

T(n)=T(n-3)+cn+2cn=T(n-3)+3cn ----(6)

Substitute equation (4) in equation (6).

T(n)=T(n-3)+cn+3cn=T(n-4)+4cn ----(7)

In general, T(n) can be written as follow:

T(n)=T(n-k)+i=1nci ----(8)

Substitute then equation (8) can be represented as follows:

T(n)=T(0)+i=1nci=T(0)+c0+c1+...+cn=T(0)+(c(n+1)-1)/(c-1)

Note:

The geometric progression of c0+c1+...+cn can be represented as cn+1-1c-1.

Let T(0)=1. Thus, the running of T(n depends only on the value of “cn” which is as follows:

T(n)=1+cn=O(cn)Therefore,T(n)=O(cn) ----(9)

(j)

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

T(n-1) can be represented as follows:

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

T(n-1) can be represented as follows:

T(n-2)=2T((n-2)-1)+1=2T(n-3)+1 ----(3)

T(n-3)can be represented as follows:

T(n-3)=2T((n-3)-1)+1=2T(n-4)+1 ----(4)

Substitute equation (2) in equation (1). Hence, T(n)can be rewritten as follows:

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=4T(n-2)+3 ----(5)

Substitute equation (3) in equation (5)

T(n)=4T(n-2)+3=4(2T(n-3)+1)+3=8T(n-3)+4+3=8T(n-3)+7

----(6)

Substitute equation (4) in equation (6).

T(n)=8T(n-3)+7=8(2T(n-4)+1)+7=16T(n-4)+8+7=16T(n-4)+15 ----(7)

In general, can be written as follow:

T(n)2kT(n-k)+i=1n-12i ----(8)

Substitute then equation (8) can be represented as follows:

localid="1658985502639" T(n)=2nT(0)+i=1n-12i=2nT(0)+20+21+...+2n-1=2nT(0)+2n-12-1

Note:

The geometric progression of 20+21+...+2n-1can be represented as 2n-12-1.

LetT(0)=1..

Thus, the running of T(n) depends only on the value of “ 2n” which is as follows:

T(n)=2n+2n-1=O(2n)Therefore,T(n)=O(2n)

(k)

The recurrence relation is shown below:

T(n)=T(n)+1=T(n12)+1 ----(1)

T(n12) can be represented as follows:

Tn12=T(n12)+1=Tn14+1 ----(2)

Tn14 can be represented as follows:

Tn14=Tn14+1=Tn18+1 ----(3)

Tn18can be represented as follows:

Tn18=Tn18+1=Tn116+1 ----(4)

Substitute equation (2) in equation (1). Hence, can be rewritten as follows:

Tn=Tn14+2=Tn18+1+2=Tn18+3 ----(5)

Substitute equation (3) in equation (5).

Tn=Tn14+2=Tn18+1+2=Tn18+3 ----(6)

Substitute equation (4) in equation (6).

Tn=Tn18+2=Tn116+1+3=Tn116+4 ----(7)

In commonly, been written as follow:

Tn=Tn12k+k ----(8)

The equation (8) can be represented as follows:

T(n)=b+k

Here, the small continue n12 is expressed as b & it’s define size of base case. Thus, k is similar to role="math" localid="1658986822994" O(loglogn).

Going time for algorithm is T(n)=O(loglogn)

So, here algorithm takes time for O(loglogn).

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

In Section 2.1 we described an algorithm that multiplies two n-bit binary integers x and y in time na, where a=log23. Call this procedure fast multiply (x,y).

(a) We want to convert the decimal integer 10n(a 1 followed by n zeros) into binary. Here is the algorithm (assume n is a power of 2):

function pwr2bin(n)

if n = 1: return10102

else:

z= ???

return fastmultiply(z,z)

Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.

(b) Next, we want to convert any decimal integer x with n digits (where n is a power of 2) into binary. The algorithm is the following:

function dec2bin(x)

if n=1: return binary [ x ]

else:

split x into two decimal numbers xt,xRwith n/2 digits each

return ???

Here binary [.] is a vector that contains the binary representation of all one-digit integers. That is, binary role="math" localid="1659333641173" [0]=02, binary [1]=12, up to binary [9]=10012. Assume that a lookup in binary takes 0(1) time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it.

A kway merge operation. Suppose you have ksorted arrays, each with nelements, and you want to combine them into a single sorted array ofkn elements.

(a)Here’s one strategy: Using the merge procedure from Section 2.3, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of kand n?

(b) Give a more efficient solution to this problem, using divide-and-conquer.

A binary tree is full if all of its vertices have either zero or two children. Let Bndenote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of B3, B5, and B7. Why have we left out even numbers of vertices, like B4?

(b) For general n, derive a recurrence relation for Bn.

(c) Show by induction that Bnis Ω(2n).

Question: On page 66 there is a high-level description of the quicksort algorithm.

(a) Write down the pseudocode for quicksort.

(b) Show that its worst - case running time on an array of size n is Θ(n)2.

(c) Show that its expected running time satisfies the recurrence relation.

T(n)O(n)+1ni=1n-1(Ti+Tn-i)

Then, show that the solution to this recurrence is O(nlogn).

In Section 1.2.3, we studied Euclid’s algorithm for computing the greatest common divisor (gcd) of two positive integers: the largest integer which divides them both. Here we will look at an alternative algorithm based on divide-and-conquer.

(a) Show that the following rule is true.

gcd(a,b)={2gcd(a2,b2)ifa,bareevengcd(ab2)ifaisodd,bisevengcd(a-b2,b)ifa,bareodd

(b) Give an efficient divide-and-conquer algorithm for greatest common divisor.

(c) How does the efficiency of your algorithm compare to Euclid’s algorithm if a and b are n-bit -bit integers? (In particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.)

See all solutions

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free