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

time complexity
Автор red_coder, 12 лет назад, По-английски

guys can u suggest me the different maximum values of N so that my program runs in time limit of 2 second for different complexities!!! Like if my complexity is O(N) then whats the maximum N for which my program would run in 2 second time limit? Similarly please also tell maximum N for O(N^2), O(N^3), O(logN), O(N*logN), O(2^N), ......etc.

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

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Ordinary computer processes about 10^8-10^9 operations per second. Codeforces machines are fast, so this number is about 10^9. You can easyly calculate expected value of N. But answer to your question depends on constant in your algorithm. So, n2 = O(n2) and 1000000000 * n2 = O(n2), but second number is much more.

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

    I guess codeforces machines are really fast, as my solution of Problem B in last contest will run in O(2 * 10^8) = ( 20 * 1000 * 1000 * 9 ) in worst case and it passed system test in 0.220 sec!! here is the link

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

O(N) – 108

O(N2) – 104

O(N3) – 200

O(logN) –  very big number

O(2N) – 24

UPD: Of course, it depends on constant, but in general it is not so high

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks friends for ur lovely answer

→ Ответить
»
12 лет назад, # |
← Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

The answers posted above are for C and c++..For java , the value of N should be somewhere near 2*n^7 for O(N) solutions..Similarly adjust for other time complexities..It also depends on constant values and what data types u use..For eg.look at my solution for #128 Problem C..Using Strings 1860609 getting TLE and same solution using StringBuilder 1860654 getting accepted ..

And ofcourse at the end of the day it also depends on the hardware configurations ..So for codechef which runs on Pentium III you decrease the value :(

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1#SECTION00080000000000000000

→ Ответить