Please help solve the time complexity of recurrence

Question

I do not know if I am solving this correctly but what I have done is analyzing the run time for the algorithm by step by step walk through and counting the executed statements. Also, what will be the big-O?

STATEMENTS  STEPS
1   if n = 0 then ▷ Terminal condition. **1**
2   f1 ← ShiftRight(b, 2n−1)    **n-1**
3   f0 ← b ⊕ ShiftLeft(f1, 2n−1)    **n-1**
4   f2 ← f0 ⊕ f1;   **n-1**
5   p2 ← Recursive (f2, n − 1); ▷ p2 is the upper half of binary **t(n/2)**
6   p0 ← Recursive(f0, n − 1); ▷ p0 is the lower half of binary  **t(n/2)**
7   return ShiftLeft(p2, 2n−1)  **n-1**

So, in the worst case, we'll have done 1+ (n−1) + (n−1) + (n−1) +t(n/2) +t(n/2) +n-1 computations, for a total run time.

T(n)= 1+ (n−1) + (n−1) + (n−1) +t(n/2) +t(n/2) +n-1 T(n)=4(n – 1) +2t(n/2) +2

Answer 1

Use the Master Theorem: you have $1= \log_2(2)$ and $f(n) = \Theta (n^{c}\log^kn)$ where $k = 0$, thus $T(n) = \Theta(n^{c}\log^{k+1}n)$, i.e., $T(n) = \Theta(n\log n)$.