Algorithm complexity using iteration method

Question

I want to find the complexity of

$$T(n) = T\left(\frac{n}{2}\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right)$$ by iteration method.

Assume $T(1) = 1$. \begin{align*} T(n) &= T\left(\frac{n}{2}\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right)\\ &= T\left(\frac{n}{2^2}\right) + \frac{n}{2} \left(\sin\left(\frac{n}{2}-\frac{π}{2}\right) +2\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right)\\ &= T\left(\frac{n}{2^3}\right) + \frac{n}{2^2} \left(\sin\left(\frac{n}{2^2}-\frac{π}{2}\right) +2\right) + \frac{n}{2} \left(\sin\left(\frac{n}{2}-\frac{π}{2}\right) +2\right)\\ &\mathrel{\phantom{=}}{}+ n \left(\sin\left(n-\frac{π}{2}\right) +2\right)\\ &=\cdots\\ &= T\left(\frac{n}{2^k}\right)+ n \sum_{i = 0}^{k-1} \frac{1}{2^i} \sin\left(\frac{n}{2^i} - \frac{π}{2}\right) + 2n \sum_{i = 0}^{k-1} \frac{1}{2^i}\\ &= T\left(\frac{n}{2^k}\right)+ n \sum_{i = 0}^{k-1} \frac{1}{2^i} \sin\left(\frac{n}{2^i} - \frac{π}{2}\right) + 2n \frac{1-(\frac{1}{2})^{k}}{1-\frac{1}{2}}. \end{align*}

Now, how to I can simplify the second summation?

Thanks.

Answer 1

We know that: $sin(x-\frac{\pi}{2})=-sin(x)$

For the second sum ($S_2$):

$\displaystyle S_2=n \sum_{i = 0}^k \frac{1}{2^i} \sin(\frac{n}{2^i} - \frac{π}{2})=-n \sum_{i = 0}^k \frac{1}{2^i} \sin(\frac{n}{2^i})=\Im ( -n \sum_{i = 0}^k \frac{1}{2^i} e^{j(\dfrac{n}{2^i})} ) =-n \Im( \sum_{i = 0}^k \frac{e^{j(\dfrac{n}{2^i})}}{2^i} )$

This is also a geometric sequence. Note that $\Im$ stands for imaginary part of the number and $\Im (e^{xj})=sin(x)$.

$$\displaystyle\to S_2= -n \Im ( \sum_{i = 0}^k \frac{e^{j(\dfrac{n}{2^i})}}{2^i} )=-n \Im(\dfrac{1-\frac{e^{j(\dfrac{n}{2})(k+1)}}{2^{(k+1)}}}{1-\frac{e^{j(\dfrac{n}{2})}}{2}})$$

We now multiply numerator and denominator by the conjugate of denominator to separate the real and imaginary part:

$$\to S_2=-n \Im \bigg(\displaystyle\dfrac{1-\frac{e^{j(\dfrac{n}{2})(k+1)}}{2^{(k+1)}}}{1-\frac{e^{j(\dfrac{n}{2})}}{2}} \times \frac{1+\frac{e^{j(\dfrac{n}{2})}}{2}}{1+\frac{e^{j(\dfrac{n}{2})}}{2}} \bigg)=-n\Im \bigg(\dfrac{1+\frac{e^{j(\dfrac{n}{2})}}{2}-\frac{e^{j(\dfrac{n}{2})(k+1)}}{2^{(k+1)}}-\frac{e^{j(\dfrac{n}{2})(k+2)}}{2^{(k+2)}}}{1-\dfrac{e^{nj}}{2}}\bigg)=-n\Im \bigg(\dfrac{1+\frac{e^{j(\dfrac{n}{2})}}{2}-\frac{e^{j(\dfrac{n}{2})(k+1)}}{2^{(k+1)}}-\frac{e^{j(\dfrac{n}{2})(k+2)}}{2^{(k+2)}}}{1-\dfrac{(-1)^n}{2}}\bigg)=-\dfrac{n}{1-\dfrac{(-1)^n}{2}}\Im \bigg({1+\frac{e^{j(\dfrac{n}{2})}}{2}-\frac{e^{j(\dfrac{n}{2})(k+1)}}{2^{(k+1)}}-\frac{e^{j(\dfrac{n}{2})(k+2)}}{2^{(k+2)}}}\bigg) $$

$\displaystyle\to S_2=-\dfrac{n}{1-\dfrac{(-1)^n}{2}} \bigg( \dfrac{\sin(\dfrac n2)}{2} - \dfrac{\sin(\dfrac {n}{2} (k+1))}{2^{k+1}} - \dfrac{\sin(\dfrac {n}{2} (k+2))}{2^{k+2}} \bigg)$

Answer 2

The term to be simplified is a combination of $\sum 2^k\cos 2^k$ and $\sum 2^k\sin 2^k$ or collectively $\sum 2^ke^{i2^k}$.

As far as I know, there is no closed form expression for such a "super-geometric" summation.

Anyway, using that $|e^{it}|\le1$, the absolute value of the sum is bounded by $2n$.