(Solved): Example 1. Solve the following recurrence relation T(n)=2T(n/2)+n 1. Draw a recursion tree based o ...

Example 1. Solve the following recurrence relation $$T(n)=2T(n/2)+n$$ 1. Draw a recursion tree based on the given recurrence relation. - A problem of size $$\mathrm{n}$$ is divided into 2 subproblems of size $$n/2$$. - Each subproblem of size $$n/2$$ is divided into 2 subproblems of size $$n/4$$ and so on. - At the bottom layer, the size of subproblems reduces to 1. 2. Substitute the above recursive tree with the following recursive tree where each node represents the cost of the corresponding subproblem: 3. Determine the cost of each level - Cost of level-0 $$=\mathrm{n}$$ (the first level) - Cost of level-1 $$=n/2+n/2=n$$ (the second level) - Cost of level $$?2=n/4+n/4+n/4+n/4=n$$ and so on. 4. Determine the total number of levels in the recursion tree - Size of subproblem at level $$0=n/2^0$$ - Size of subproblem at level- $$1=n/2^1$$ - Size of subproblem at level $$2=n/2^2$$ - Size of subproblem at level-i $$=n/2^i$$ - Size of subproblem at the last level $$1=n/2^x$$, so $$x={\log }_{2}n$$ - So, the total number of levels in the recursion tree $$={\log }_{2}n+1$$ 5. Determine number of nodes in the last level - Level-0 has $$2^0$$ nodes i.e. 1 node - Level-1 has $$2^1$$ nodes i.e. 2 nodes - Level-2 has $$2^2$$ nodes i.e. 4 nodes - Level- $${\log }_{2}n$$ has $$2^{{\log }_{2}n}$$ nodes $$=n$$ nodes 6. Determine cost of last level - Cost of last level $$=n\times T(1)=n$$ 7. Add costs of all the levels of the recursion tree and simplify the expression in terms of asymptotic notation: - $$T(n)=\{n+n+n+\dots \}+n=n\times {\log }_{2}n+n=n{\log }_{2}n+n=O(n\log n)$$ 7. Add costs of all the levels of the recursion tree and simplify the expression in terms of asymptotic notation: - $$T(n)=\{n+n+n+\dots \}+n=nx{\log }_{2}n+n=n{\log }_{2}n+n=O(n\log n)$$ To answer the following questions, use the following notations: 1. To show exponentiation, use a caret sign $${}^{?};$$ for example, $$n^3$$ should be $$n^{?}3$$ 2. To show a logarithm, use parentheses; for example, $${\log }_{2}n$$ should be $$\log 2(n)$$ \# How many levels the following recurrence $$T(n)=2T(n/3)+n$$ has? \# What is the cost of the first level (corresponds to level-0)? \# What is the cost of the second level (corresponds to level-1)? \# What is the cost of the last level? \# What is the cost of the whole tree? $$\mathrm{n}?>?$$