
	Home


	Homework Help


	Answer Board


	Resources (Beta)

You Are Here:

Home > Answer Board > Computer Science > Topic: cs502 Algo i need complite Assignment..Solve the foll...

Member's Topic Headline:

cs502 Algo i need complite Assignment..Solve the following recurrence relations and show its running time using asymptotic notations. You may assume that T(1) = 1 a) T(n) = T(sqrt(n))+1 b) T(n) = 2T(n-1)+1...(Calculate the T complexity of the follow)

Know the answer? Have a better solution? Share it.

Get Help Now.

View homework problems
explained for free!

Question:

a1a1a1

Rookie

Karma Points: 9

Date Posted: 5/16/2008 1:58:49 PM Status: Live

Asker's Rating: Lifesaver

Response:

part (b):

T(1) = 1 = 2⁰ = 2^1-1

T(2) =2T(2-1)

= 2T(1)

= 2= 2¹ = 2^2-1

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

= 2T(2)

= 4= 2² = 2^3-1

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

Asymptotic Solution of the given recurrence

Since T(n) =2^n-1

T(n) = O(2ⁿ)

By reading or posting messages on these forums, you are agreeing to the Answer Board's Terms of Service and Conduct (TSC).