1
vote
1answer
85 views

What sequences / algorithms does $O(N \log\log N)$ limit?

Considering the big-o-notation, there are a variety of algorithms that have the $O(N \log N)$ computational complexity; such algorithms are for example the merge sort, fast fourier transform, etc. ...
1
vote
1answer
31 views

Prove that for n~=n' sum is much smaller than the case with n=n'

Hi I want to prove that this summation is much smaller for $n\neq n'$ than for the case where $n=n'$. I have seen this fact with simulation results. But I don't know how to prove it in mathematics. ...
1
vote
0answers
78 views

Expansion in powers

Let $n=2k, k \in Z_+$. Let $$P_k\left(\frac{t}{\sqrt n}\right)=n!\sum_{\begin{smallmatrix} n_1+\ldots+n_k=n \\ ...
0
votes
1answer
37 views

Number of steps to eliminate all elements from an array, reducing by a decreasing fraction

Assume I have an array of $N$ (say $N$ very large) elements. I proceed removing $1/2$ of the elements then, from what remains, I remove $1/3$ of the elements, then, from what remains, i remove $1/4$ ...
0
votes
2answers
103 views

Find the rate of growth for $\sum_{n=1}^N 1/n^p$ in term of big $O$ notation

Find the rate of growth for $$ \sum_{n=1}^N \frac{1}{n^p} $$ in term of big $O$ notation for the three cases $0 < p < 1$, $p=1$ and $p>1$. It seems the question can be approached by ...
5
votes
2answers
426 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
0
votes
1answer
251 views

Finding a Big-O notation of: $\sum\limits_{i=1}^{k} ( t(a_i n)) + n$

I'm trying to find a Big-O notation of: $\displaystyle\sum_{i=1}^{k} ( t(a_in)) + n$, where $\displaystyle\sum_{i=1}^{k} (a_i) < 1$ using a recursion tree method and substitution method. I've ...