Time complexity for an algorithm involving two for loops

Question

public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int n = sc.nextInt();
  int m = sc.nextInt();
  int result = 0;

  for (int i=0; i < n; i++) {
    for (int j=m; j > 0; j--)
      result += 1;
    m -= 1;

  }
  System.out.println(result);
}

The question is a true or false question. The statement is "The time complexity of the following program when n is much bigger than 2m is O(nm)". True or False?

The time complexity in the question refers to the worst case time complexity. This is what I have done so far:

Inner loop runs m times and the value of m decreases by 1 each time. The total number of iterations of the inner loop is then: m + m - 1 + m - 2 + m - 3 + .... + 3 + 2 + 1.

We can consider this to be a arithmetic sequence.

The total number of iterations of the inner loop is then: m(m + 1)/2 = (m² + m)/2.

After m has reached 0, since n is much bigger than 2*m, the outer loop will continue to run in O(1) time for n - m times more.

So, the time complexity is: (m² + m)/2 + n - m = O(m²).

Is this the correct way to approach this question?

Answer 1

No, that's not correct. First of all, there is no "worst case" or "best case" here, since the number of steps is completely determined by n and m.

The question is, as you stated, a yes/no question. So simply calculating the time complexity is not the right approach to this question (and btw, the result is not O(m^2) - you can't just drop the n!).

Your reasoning up to the last step is correct. The number of steps is, as you correctly calculated, (m^2 - m)/2 + n (after simplification). The question is: is (m^2 - m)/2 + n a member of the set O(mn), under the assumption that n >> 2m?

Ignoring constants for simplicity, let's write down the hypothesis as inequality:

(m^2 - m)/2 + n < nm (eventually, as n, m grow)

Now dividing by nm on both sides yields the equivalent inequality

(m - 1)/(2n) + 1/m < 1

By the assumption, the first term vanishes, so we are left with 1/m < 1 which is clearly true as m grows. Hence the hypothesis is correct, and the answer is yes.