Блог пользователя Noble_Mushtak

Confused about Complexity of Contest 362 Div. 1 Problem A:
Автор Noble_Mushtak, история, 8 лет назад, По-английски

Here is my analysis of the solution to Contest 362 Div. 1 Problem A:

  • There are edges per query.
  • Each edge takes to process. There are added every query and O(q) queries, so we have edges, meaning each edge is to process.
  • Finally, there are O(q) queries.

This gives us overall. However, the editorial does not have the term and simply has . How did they get rid of the term in the analysis? Did I do something wrong here?

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

The theory of the matchstick. Theoretically, you can elaborate the complexity how much you want, but it is not necessary. That log(log(log(VMAX))) is just too small to be taken in account: log(log(log(1010000000))) ≈ 2.83.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    This is only two s, not three. Compared to the term that it is next to inside the parentheses, it is not negligible:

    Unable to parse markup [type=CF_TEX]

    Unable to parse markup [type=CF_TEX]

    However, I see now how it is the smaller term, so they ignored it.

    → Ответить