PP$09$ Consider the recurrence given below: T$($n$)=2.$TL$)+1.$ With the boundary conditions given as T$(1)=$T$(2)=$T$(3)=1$ Part $1-$ Solve T$($n$)$ for recurrence, make use of the recursion tree method, solve the recurrence for T$($n$)$ when n is a power of $4.$ Use the answer to guess what big$-$O notation is for T$($n$)$ Part $2-$ Use the substitution method to prove that the guess for big$-$O notation.