Time complexity for this algorithm?

Question

If I don't have a condition in the second loop the time complexity will be $O(n^2)$ from:

$$\sum_{i=0}^{n}\sum_{j=0}^{m}c$$

So what happens in this case:

int n = 5;
int m = 10;
int rnd; //rnd is a random number between 0 and m
for(int i=0; i<n; i++)
{
    for(int j=0; j<m; j++)
    {
       if(j==rnd) 
          break;
    }
}

Is it $O(n)$ or still $O(n^2)$. Or I have to proof it in best, average and worst case?

Answer 1

First of all I give the definitions of the operators, the way I use them.

$f(n) = O(g(n))$ means $$\exists_{k>0} \exists_{n_0} \forall_{n > n_0} \ f(n) \leq k g(n)$$

$f(n) = \Omega(g(n))$ means $$\exists_{k>0} \exists_{n_0} \forall_{n > n_0} \ f(n) \geq k g(n)$$

$f(n) = \Theta(g(n))$ means $$\exists_{k_0 > 0} \exists_{k_1 > 0} \exists_{n_0} \forall_{n > n_0} \ k_0 g(n) \leq f(n) \leq k_1 g(n)$$

I'll call the integer random value $r$, and $0 \leq r \leq m$.

Furthermore I assume that the distribution of $r$ is uniform. Hence every value between $0$ and $m$ is equally likely.

The best that can happen is that $r = 0$. This eliminates the inner loop. The remaining number of iterations is $n$. The complexity of the algorithm in this special case is obviously $O(n)$. Every iteration consists of a fixed number of low level operations. Hence the upper bound is given by $O(n)$. The lower bound is given by $\Omega(n)$. Therefor in the best case of $r = 0$, the complexity of the algorithm is $\Theta(n)$.

The worst that can happen is that $r = m$. The number of iterations will be $nm$. This yields an upper bound of $O(nm)$, and by the same reasoning as above, a lower bound of $\Omega(nm)$. The worst case complexity of the algorithm is $\Theta(nm)$.

On average, $r = \frac{1}{2}m$, due to the uniform distribution. The number of iterations will be $\frac{1}{2}nm$. Because the multiplier $\frac{1}{2}$ vanishes in the big $O$ notation, the complexity will still be $O(nm)$.

This means, that the algorithm as a whole has a complexity of $O(nm)$, with a lower bound of $\Omega(n)$. Because of the different functions ($n \neq nm$), the complexity of the algorithm cannot be expressed in the $\Theta$ notation.