### twocf22's blog

By twocf22, history, 7 days ago,

#### 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.

• -35

 » 7 days ago, # | ← Rev. 2 →   -12 Same (both algorithms work for $O(n^2)$, of course, if $n$ is not fixed in advance)
•  » » 7 days ago, # ^ |   0 It looks as if the second code solves another problem in which $n$ is fixed.
•  » » » 7 days ago, # ^ |   0 If n is fixed, will the second code get accepted?
•  » » » » 7 days ago, # ^ | ← Rev. 2 →   0 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, # |   -7 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, # ^ |   0 Thank you! <3 Now it is clear to me.
 » 7 days ago, # |   0 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, # |   +5 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, # ^ |   +9 Writing 10^12 if statements is a good idea!
 » 7 days ago, # |   0