twocf22's blog

By twocf22, history, 7 days ago, In English

First Code:

int ans = 0;
for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    if ((i + j) % 2 == 0) ans += 1;
  }
}

The time complexity of this code is $$$O(n^2)$$$

Second Code:

if ((1 + 1) % 2 == 0) ans += 1;
if ((1 + 2) % 2 == 0) ans += 1;
if ((1 + 3) % 2 == 0) ans += 1;
if ((1 + 4) % 2 == 0) ans += 1;
if ((1 + 5) % 2 == 0) ans += 1;
.........
if ((n + n) % 2 == 0) ans += 1;

Is the time complexity of this code same as the first code? Or is it $$$O(1)$$$ ?.

Thank You.

 
 
 
 
  • Vote: I like it
  • -35
  • Vote: I do not like it

»
7 days ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

Same (both algorithms work for $$$O(n^2)$$$, of course, if $$$n$$$ is not fixed in advance)

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It looks as if the second code solves another problem in which $$$n$$$ is fixed.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If n is fixed, will the second code get accepted?

      • »
        »
        »
        »
        7 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It does not depend on the time complexity of the solution whether it will get AC or not. It all depends on the number of simple operations that your solution performs. Your solution can work for a very long time due to the fact that it performs a lot of actions, but at the same time it has a complexity of $$$O(1)$$$, just because it does not depend on the input data.

»
7 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Relate to time complexity as no. of operations. For the first case, the outer loop is running n times and the inner loop is running n times , the complexity of each operation inside both loops is O(1), so the time complexity of code-1 is O(n*n*1), for the 2nd code , there are n*n O(1) operations , so no. of operations is O(n^2) for this case also.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The complexity of the second code (assuming you wrote it for some specific $$$n$$$) is $$$O(1)$$$. Do not confuse running time and time complexity.

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

I am sorry for my stupid question. Today I was solving a problem where $$$n \leq 10^6$$$
I couldn't find an efficient way to solve. But then I thought, if I write $$$n^2$$$ if — else, may be it will get accepted.

Now everything is clear to me. I am again sorry for my stupid question.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it