UNIT 1 QB.pdf


Preview of PDF document unit-1-qb.pdf

Page 1 2 3 4 5 6 7 8

Text preview


19. Solve the recurrence relation X(n)=X(n-1)+5 for n>1, X(1)=0

20. Solve the recurrence relation X(n)=X(n-1)+n for n>0, X(0)=0

21. Solve the recurrence relation X(n)=3X(n-1) for n>1 X(1)=4

22. Solve the recurrence relation T(n)=8T(n/2)+n2 using Master’s
Theorem.
Mapping with general EQN. a = 8, b = 2, d = 2
bd = 22 = 4 So, a>bd then

log a
b

log 8
2

3)

23. Find the complexity of the recurrence relation
T(n)=2T(n/2)+n2
Mapping with general EQN.
a = 2, b = 2, d = 2
bd = 22 = 4 So, a < bd

log a
b

d

24. Solve the recurrence relation x(n)=x(n/3)+1

2)