1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ How big your tree of recursive calls can be if the function's input decreases half the original? First assume $n$ is some power of $2$ so your equation looks easier: $n = 2^m \Rightarrow T(2^m) = 4\cdot 2^m + 2T(2^{m-1}) -2$. $\endgroup$ – Gilberto López Jul 21 '17 at 4:04
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.