[Math] Time complexity of random algorithm

Question

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$.

At first I thought to perform the analysis by saying that incremen, decrem, and MultiDecremen are called $n/3$ each one, but the fact that $O(n²)$ and $\Theta(n)$ got me confused.

public static int increm(int n){if(n==0) return 0; else return ++n;}
public static int decrem(int n){if(n==0) return 0; else return --n;}
public static int MultiDecrem(int n, int k){
    while(n != 0 && k !=0){
        n=decrem(n);
        k--;
    }
    return n;
}
public static void main (String...args){
    int n = args[0];
    final int seed = args.length > 1 ? Integer.parseInt(args[1]) : (int) System.currentTimeMillis();
    final Random random = new Random(seed);
    int compt=n;
    while(compt--!=0){
        int alea = random.nextInt(3);
        if(alea==0) n=increm(n);
        if(alea==1) n=decrem(n);
        if(alea==2) n=MultiDecrem(n,n/2);
    }
}

Answer 1

Obviously the time complexity is $\Omega(n)$, because the outer loop runs $n$ times.

Similarly, the time complexity is $O(n^2)$, because the complexity of MultiDecrem is $O(n)$.

Finally, consider that MultiDecrem was called $k$ times. Naturally, decrem helps us, so let's assume that the rest were increm calls and denote their number between $(i-1)$-th and $i$-th MultiDecrem as $a_i$. This gives a bound for the total number of operations that MultiDecrem preforms (modulo missing ceil and floor functions)

\begin{align} (n+a_0)/2+((n+a_0)/2+a_1)/2 + \ldots \leq n + a_0 + a_1 + a_2 + \ldots + a_k \leq 2n \end{align} because $\sum_i a_i \leq n$. Hence, the algorithm is $O(n)$ and so $\Theta(n)$ as well.

I hope this helps $\ddot\smile$