CODEWITHSUNDEEP
algorithm
algo-geeks
algo-geeks

Reputation: 5438

recurrence relation for tree

suppose there is a tree with number of child nodes increasing from 2 to 4 then 8 and so on.how can we write recurrence relation for such a tree.

Upvotes: 0

Views: 566

Answers (2)

vaibhav
vaibhav

Reputation: 11

  • using subtitution method- T(n)=2T(n/2)+n =2[2T(n/2^2)+n/2]+n =2^2T(n/2^2)+n+n =2^2[2T(n/2^3)+n/2^2]+n+n =2^3T(n/2^3)+n+n+n

    similarly subtituing k times-- we get

    T(n)=2^k T(n/2^k)+nk the recursion will terminate when n/2^k=1 k=log n base 2.

    thus T(n)=2^log n(base2)+n(log n) =n+nlogn

    thus the tight bound for the above recurrence relation will be =n log N (base of log is 2)

Upvotes: 1

rkg
rkg

Reputation: 5719

Take a look at this link.

T(n) = 2 T(n/2) + O(n)         [the O(n) is for Combine]
T(1) = O(1)

Upvotes: 0

Related Questions