Advanced algorithms design and analysis Question 1 (15 POINTS): Usng asymptotic

Question

Advanced algorithms design and analysis

Question 1 (15 POINTS): Usng asymptotic upper bound definition for "O", show that 20+1-0(2) Please show your work. Question 2. (20 POINTS): Given the recurrence: T(n) T(n- 1)+1 use substitution method to check whether T(n)-?(n). Please show your work. Question 3. (20 POINTS - 10 POINTS each) Gnen folowing recurences, use recursion tree method to determine the asymptotic bound or each recurrence. Please show your work .A) T(n)- T(n -1)+ n 3.B.) T(n)-2T (2) + n

Explanation / Answer

Answer:

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

Using Substitution Method

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

Using 1 in A , we have

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

=> T(n) = T(n -2) + 2 ----------(B)

.

.

.

T(n) = T( n - k) + 1*k

Let n = k

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

T(n) = 0 + n

T(n) = theta(n)

DEAR PLEASE DO RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

DUE TO COMPANY NORMS , WE ARE RESTRICTED TO ANSWER A SINGLE QUESTION FROM MULTIPLE POSTED QUESTIONS. KINDLY POST SEPARATELY TO GET ANSWERED.

THANK YOU!!!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.