red_coder's blog

time complexity
By red_coder, 12 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

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

    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

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    100002 = 108

    20003 = 8 * 109

    224 = 1.6 * 107 + eps

    Very strange numbers =)

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

    Umm.. so, could anyone tell me what the time complexity for O(10^12), is??

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks friends for ur lovely answer

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

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 :(

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply