Noble_Mushtak's blog

Confused about Complexity of Contest 362 Div. 1 Problem A:
By Noble_Mushtak, history, 8 years ago, In English

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?

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply