#recurrence relation

Question

Given below are some recurrence relation and some asymptotic complexities -

listA                                                                    listB

A) T(n) = T(n-1) + 1/n                                 1) Big theta(n log log n)

B) T(n) = 2T(n/2) + n/logn                          2) Big theta (n^2.5)

C) T(n) = sqr root (n).T(sqr root (n)) + n    3) Big theta(log log n)

D) T(n) = 4T(n/2) + n^2(sqr root(2))          4) Big theta(log n)

Codes :

    A  B C D

a) 4  1  2  3

b) 4  1  1  2

c) 1  4  3  2

d) 3  1  1  2

Correct ans  = b

Answer 1

Option B is the answer.

1. T(n) = T(n-1) + 1/n
Apply substitution ,
T(n) = 1+1/2 + 1/3 + 1/4 +1/5 +... +1/n

T(n) = O(logn)

2.  T(n) = 2T(n/2) + n/logn

Apply master theorem
T(n)= O(nloglogn)

3.T(n) = sqr root (n).T(sqr root (n)) + n

T(n)= O(nloglogn)

4.T(n) = 4T(n/2) + n^2(sqr root(2))  

Apply master theorem
T(n)= O(n^2.5)

Comments

How are u calculating time complexity without any base conditions for 1st and 3rd equations ?

---

how are you solving B using masters theorem plz give the steps

---

Master’s thrm cannot be applied to B.
https://www.cs.cornell.edu/courses/cs3110/2014sp/recitations/24/using-the-substitution-and-master-method.html