-1

What's the run-time complexity of the following code

public void foo (int n, int m)
{
   int i = m;
   while (i > 100)
      i = i/3;
   for (int k=i ; k>=0; k--)
   {
      for (int j=1; j<n; j*=2)
         System.out.print(k + "\t" + j);
      System.out.println();
   }
}

I think it's O(log n), But I'm not sure about the first for loop. It runs maximum 100 times, but log n in every iteration.

EDIT: It's not a duplicated of How to find time complexity of an algorithm since I know how to find time complexity, but this specific case was a bit tricky so I asked only about this one, I didn't ask how to find time complexity in general. Like the fact that I know how to play football in general, doesn't mean I can kick like messi, maybe I need some explanation on how to do it, but I don't need explanation of what is football etc.

Community
  • 1
  • 1
Avishay28
  • 2,288
  • 4
  • 25
  • 47

4 Answers4

2

First loop is 0(log m), as iterations give i the values m/3, m/9, m/27...

The inner loop (on j) executes its body log n times, and itself is executed at most 100 times

So the complexity is O(log(m)) + O(log(n))

Michel Billaud
  • 1,758
  • 11
  • 14
0

Let's look at the first loop first:

int i = m;
while (i > 100)
   i = i/3;

Can be described as T(i) = O(1) + T(i/3), since you're doing some const work (condition comparison etc.) and then reiterating the loop with a value smaller by a third. If we'll expand it by recursion, we'll get:

T(i) = O(1) + T(i/3)
     = O(1) + O(1) + T(i/3/3) = 2*O(1) + T(i/9)
     = 2*O(1) + O(1) + T(i/9/3) = 3*O(1) + T(i/27)
     = ... = n*O(1) + T(i/3^n)

The last statement being for the n-th iteration. Now, the loop would stop i/3^n <= 100 which means when n = log3(i/100). So you'll do log(i) operations, which means the first loop's complexity is O(log(i)). (note that you've set i=m so this is basically O(log(m))).

Now let's look at the second loop:

for (int k=i ; k>=0; k--) {
   for (int j=1; j<n; j*=2)
      System.out.print(k + "\t" + j);
   System.out.println();
}

The inner loop can be described as T(n) = O(1) + T(2*n). Let's expand:

T(j) = O(1) + T(2j) = O(1) + O(1) + T(2*2j) = 2*O(1) + T(4j)
     = 2*O(1) + O(1) + T(2*4j) = 3*O(1) + T(8j)
     = ... = l*O(1) + T((2^l)*j)

Again, the last one being for the l-th iteration. So you'll stop once (2^l)*j = n, which means when j=log(n). So the inner loop complexity is O(log(n)).

Now let's look at the outer loop. It could be described as T(k) = O(log(n)) + T(k-1). Let's expand:

T(k) = O(log(n)) + T(k-1) = O(log(n)) + O(log(n)) + T(k-1-1) = 2*O(log(n)) + T(k-2)

By this point, I'm sure you can see that by the l-th iteration you'll have l*O(log(n)) + T(k-l). You'll stop once k-l < 0 so when k=l and so the complexity is O(k*log(n)).

But what is k? Well, k is basically set to the value of i which is m chopped down log3 times. So you'll be doing log(n) work for log(m) times. So your complexity is O(log(m)*log(n)).

Ori Lentz
  • 3,668
  • 6
  • 22
  • 28
0

Yes you got it right it O(log(n))+O(log(m)) which is going to be O(log(n*m)) since

  • complexity of first loop is O(log(m))
  • the second loop has complexity of O(log(n))
  • Complexity ~ a * log(n)+b * log(m)
  • min(a,b) (log(n)+log(m)) < a * log(n)+b * log(m) < max(a,b) (log(n)+log(m))
  • min(a,b) < [a * log(n)+b * log(m)]/[(log(n*m))] < max(a,b)

so you can say that your expression is Order of log(n*m)

achabahe
  • 2,445
  • 1
  • 12
  • 21
-1

Since it contains 2 nested loops, and both operate on log n terms, it's

O(log m) = while loop +

O(log m * (log n)) = for loop

Base of log as 2 and 3 can be omitted.

So it comes to log mn (Max of these)

YSBoom
  • 21
  • 4