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 = (m2 + 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: (m2 + m)/2 + n - m = O(m2).
Is this the correct way to approach this question?
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments