twocf22's blog

What is the time complexity?
By twocf22, history, 3 years 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

Comments Comments (8)
| Write comment?
»
3 years 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)

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
»
3 years 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.

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Writing 10^12 if statements is a good idea!

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply