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