Mathematically calculating time complexity

Question

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.

Also I understand that it's impossible to calculate every function, but usually we can (otherwise we have not been asked to do so on the exam).

I know how to mathematically calculate the time complexity of the following function:

for(i = 0; i <= n-1; i++) {
    for(j = i + 1; j <= n - 1; j++) {
        // loop body - const O(1)
    }
}

I would calculate it as following: (hope without mistakes)

$$\begin{align*} \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1 & \overset{(1)}{=}\sum_{i=0}^{n-1}((n-1)-(i+1)+1)\\ &=\sum_{i=0}^{n-1}(n-i-1)\\ &=n\cdot\sum_{i=0}^{n-1}1-\sum_{i=0}^{n-1}i-\sum_{i=0}^{n-1}1\\ &\overset{(2)}{=}n\cdot\sum_{i=0}^{n-1}1-\sum_{i=1}^{n-1}i-\sum_{i=0}^{n-1}1\\ &\overset{(1)}{=}n\cdot((n-1)-0+1))-\sum_{i=1}^{n-1}i-((n-1)-0+1)\\ &=n^{2}-n-\sum_{i=1}^{n-1}i\\ &\overset{(2)}{=}n^{2}-n-\frac{(n-1)\cdot n}{2}\\ &=\frac{2n^{2}-2n-n^{2}+n}{2}\\ &=\frac{n^{2}-n}{2}\\ &=O(n^{2}) \end{align*}$$

when I use the following equations:

$$\sum_{i=m}^{n}1=n-m+1 \,\,\,(1)$$ $$\sum_{i=0}^{n}i=\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \,\,\,(2)$$

But when I get across with much harder function, as following:

example 1:

int x = 2;
while (n < x) {
    x *= x;
}

example 2;

int i = 1;
while(i < n) {
    if((n – i) % 2)
        i *= 3;
    else
        i *= 2;
 }

I get lost. I really don't know where to start calculating. I always can start inserting different values for n, and guessing the time complexity, but it does not feels right (and also it can be misleading).

Is it even possible to mathematically calculate the time complexity of those examples? how should I approached those questions? Maybe is there somewhere a list of possible tricks?

Answer 1

If we ignore effects of overflow and assume we can square x as often as we like in constant time, then the first example clearly either stops immediately if n ≥ 2, or runs forever if n < 2.

In the second example, at each iteration i is multiplied either by 2 or by 3. Therefore after k iterations, $2^k ≤ i ≤ 3^k$. The number of iterations until i ≥ n is between $log_2 (n)$ and $log_3(n)$ which is in each case $O (log(n))$.

On the other hand, I'm currently working on an algorithm where I don't have the slightest idea how to calculate the runtime, although measurements show that it takes experimentally about $600 n^{1/2}$ nanoseconds for values from $10^{12}$ to $10^{19}$ - with huge variations. A proof for $O(n^{1/2})$ is mathematically beyond me.

In the end, this question is like asking "how can I prove mathematical theorems". Some are easy, some are hard, most get easier with practice. There is no "list of possible tricks". The most helpful thing is that when you are concerned with big-O notation you don't need precise results. A constant factor makes no difference.