You fire given a rooted tree T with n nodes. The tree may not be binary*. You wa

Question

You fire given a rooted tree T with n nodes. The tree may not be binary*. You want to find the depth of T. Here, we define the depth of a node v in the tree to be the maximum number of nodes along a path from v to a leaf under u (going downwards). The depth of T is the depth of the root of T. Now give a divide and conquer algorithm for finding the depth of a tree. You need to analyze its running time. Solve the following recurrence. Show the steps. T(n) = {12T(n/4) + n^1.5, if x greaterthanorequalto 4 1, otherwise T(n) = {T(squareroot n) + logn, if x greaterthanorequalto 4 1, otherwise T(n) = T(n/2) + ominus(1), which is the running time of the binary search.

Explanation / Answer

4) Recurrance relations
1) T(N) = 12T(N/4 ) + n1.5
Using Masters Method to Solve the Recurrance :

T(N) = a T(N/b ) + f(n)
a = 12 , b = 4 , f(n) = n1.5
=> So nlog ba we get
=> nlog 412 = > n1.79                  That means n1.79   = n1.5 +x
=>This falls into Case 1 hence T(N) = O)(nlog ba)
=> T(N) = O(n1.79 )

2) T(N) = T(sqrt(n) + log n
Let n = 2m
Let T(2m) = T(2m/2) + m
=> And that means

S(k) = T(2m)

S(k) = S(k/2) + k

T(N) = O(log log n)



3) T(N) = T(N/2 ) + 1

a = 1 , b = 2 f(n) = 1
So, => So nlog ba we get
=> nlog 21 = > n0                  That means f(n) = n0
=>This falls into Case 2 hence T(N) = O)(log n )
=> T(N) = O(log n )

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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