# Time complexity for this algorithm?

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?

• Why $\Theta(n^2)$? It is $\Theta(nm)$. Regarding your question in the worst case, it is still $\Theta(nm)$. In the best case, it is $\Theta(1)$ and in average case I guess it is again $\Theta(nm)$ – Ahmad Feb 21 '18 at 13:19
• @Ahmad, in the best case, it is still $\Theta(n)$; the break; breaks only out of the outer loop, so the loop is entered $n$ times which still takes $\Omega(n)$ time. – Mees de Vries Feb 21 '18 at 13:21
• @Ahmad: since $n$ and $m$ only differ by a constant factor, and the complexity considerations target at large $n$ and $m$, it is OK to write $O(n^2)$. – Ronald Feb 21 '18 at 13:22
• @Ronald, nothing in the question suggests that $n$ and $m$ only differ by a constant factor in the generalized situation. – Mees de Vries Feb 21 '18 at 13:22
• @MeesdeVries OK I got your point and understand you're right. We simply know too little about $n$ and $m$, even if the program code assigns values to them. – Ronald Feb 21 '18 at 13:34

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.