1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$ $\endgroup$ – Ahmad Feb 21 '18 at 13:19
  • 2
    $\begingroup$ @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. $\endgroup$ – Mees de Vries Feb 21 '18 at 13:21
  • $\begingroup$ @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)$. $\endgroup$ – Ronald Feb 21 '18 at 13:22
  • 1
    $\begingroup$ @Ronald, nothing in the question suggests that $n$ and $m$ only differ by a constant factor in the generalized situation. $\endgroup$ – Mees de Vries Feb 21 '18 at 13:22
  • $\begingroup$ @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. $\endgroup$ – Ronald Feb 21 '18 at 13:34
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.