3. In a divide and conquer based algorithm, the recursive calls form a tree structure as shown in the following figure.

[answerhappygod]

3 In A Divide And Conquer Based Algorithm The Recursive Calls Form A Tree Structure As Shown In The Following Figure 1 (73.9 KiB) Viewed 20 times

3. In a divide and conquer based algorithm, the recursive calls form a tree structure as shown in the following figure. The size of subproblems is 1/4 of upper-level problems when generating a new level of subproblems. And the branching factor is 4 which means one problem is divided into four subproblems every time. The time to combine results of four subproblems is linear to the size of the subproblem. i.e., T(n) = 4T () +0(n), Please answer the following questions (15') How many levels of subproblems in the tree?(3¹) What is the size of each subproblem in the k-th level (the top level is k-0)? (3¹) How many sub-problems in the k-th level? (3) What is the time complexity of the k-th level?(3') Please give the total time complexity of all levels and give the Big-O notation of the time complexity (3) n n/4 n/4 n/4 n/4 |n16 n/16 n/16 n/16 n/16 |n16 n16 || nỉ 16 n/16) n/16 |n16 4 I 1 1 n/16 1