If I had in my algorithm something like this:
for (int i = 0; i < n; i++) if (i % 2) continue; else { code code code... }
Will the time complexity be O(n) or O(n / 2)?
If I had in my algorithm something like this:
for (int i = 0; i < n; i++) if (i % 2) continue; else { code code code... }
Will the time complexity be O(n) or O(n / 2)?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Strictly there are n/2 operations, but in asymptotic notation O(n) = O(n/2), so they are essentially the same (In Big O notation), because n/2 = (1/2)*n and 1/2 is a constant that is not dependent on n.
A more formal definition is to come back to the Big O definition, it means that we can find a constant k such that k*n >= n/2 for sufficiently large n. In simple words it means that n is an upper bound of n/2.
The O(n/2) is only an example. I mean, if I had something like:
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (j != 0) continue; else { code code code... }
And the expected time complexity was O(n), would this pass the test cases?
Edit: I didn't see the nested for!
Yes, that code would get TLE, because at best is O(n^2), that is if we suppose that "code..code" is O(1), if that isn't constant the complexity can be even bigger.
What are you talking about? Ofcourse answer is No! Complexity of this cycle is O(n2) even if code code code runs in O(1).
Interesting... VS optimizes this
but not this
Wouldn't pass because it will perform O(N2) operations. If you replace the continue with break then your complexity will be O(N) and it would pass. This is all assuming "code code code" runs in O(1)
Strictly there are n operations as
ifis operation too. If example is simple, like here, compiler may optimize it to run faster but it is not guarenteed.I checked this
code is disassembler. VS 2013 doesn't optimize it neither in debug nor in realise mode :(
-O2? -O3?
Both