Please read the new rule regarding the restriction on the use of AI tools. ×

luizantonioprg's blog

Do programmers calculate time complexity before they start coding ?
By luizantonioprg, history, 4 years ago, In English

I know time complexity give us an idea of the execution time of an algorithm.But in contests,what is this necessary for? Do programmers use it for something?Some problems have notations such " O(n3) ". Do they use it for calculate something before they start implementing the solution,I mean before start coding?

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

time complexity can give you an idea of what does and doesn't pass, so like i wouldn't code an n! solution for n = 1e5, because this obviously doesn't pass

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

    Can you show me a sample code?I think this would help me to understand better.

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

      So consider a problem for example 1394A - Boboniu Chats with Du, it says "maximum fun factor among all permutations of a". So what if I was thinking "ok let me try all permutations", I see that the time complexity is O(N!) and that is very big, so obviously this won't pass, so then I consider n^2 and 10^10 is still too slow so I realize I probably need an O(N) or an O(N log^2(n)) or O(N log(n)) or even faster(Note that these are estimates, sometimes you can squeeze in more)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        So in summary, time complexity is something that tells you which way to go, so understanding it is good for you to solve the problem faster, am I right?

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

          Understanding it is good for you get AC.

          → Reply