Let $a\_1,a\_2 \ldots a\_n$ be a real-valued sequense with $a\_i=O(N^{-1})$.
How do I estimate Discrete Fourier Transform (DFT) of this sequence?


$$\hat{a}\_{j}=\sum\_{r=1}^{K}a\_{r}\exp\Bigl(-2\pi ij\frac{r}{K}\Bigr),\qquad K=O(N^\alpha),\quad \alpha<1$$


Can I say that DFT sequence $\operatorname{Re}[\hat{a}\_{i}]=O(N^{-1})$?



Estimation of DFT
The answer is no, if you mean an uniform bound in $j$. Here is the example:


Fix $j$ and define
$$
 a\_r = \begin{cases} \frac{1}{N}, & Re(\exp(-2\pi i j r/ K)) \geq 0;\\\
 0, & otherwise.\end{cases}
$$
It is than easy to estimate that the number of $a\_r = \frac{1}{N}$ is comparable to $K$. Even more is true, one has that the number of $a\_r = \frac{1}{N}$ such that $Re(\exp(-2\pi i j r/ K)) \geq \sigma$ is comparable to $K$ for any $\sigma > 0$.


This implies that
$$
 Re(\hat{a}\_j) \geq c N^{1 - \alpha}
$$
for some different $c$.


