Summary

Sometimes you have a poor algorithm with a large runtime complexity, but the problem size is small. Is your algorithm good enough? Should you waste your time trying to come up with a polynomial algorithm to solve the travelling salesman problem when your problem only has 10 nodes?

Javascript not detected

Looks like you're not using javascipt. No worries I got you covered. I put together a table at the bottom of this page that achieves the same goal.

Warning

These are estimates. There are so many factors that can throw the runtimes off by 1000x like:
  1. IO
  2. Network
  3. Computer architecture
  4. Computer age
  5. The tool includes only common runtime complexities, but there infinitely many complexities inbetween the runtime complexities the tool evaluates.
  6. Coefficients and lower order terms of your algorithm's complexity (ex: N2 vs 2*N2)
  7. Concurrency
  8. Language (C, javascript, java, etc)
  9. Contention for physical resources
  10. Bugs in this tool

My Motivation

In Google Kickstart 2017 Round F, Problem 1 "Cake" , you find the minimum number of square cakes needed to cover a target area. The input size was 104 and the runtime limit was 30 seconds. I thought of a brute force algorithm that I guessed was between O(N3) and O(N6). At the time, I had no idea how long that would take. I was hoping for a resource similar to Latency Numbers Every Programmer Should Know to help me ballpark how long my algorithm would take before implementing it. I couldn't find anything so I wasted time thinking about how to make it more efficient. I eventually gave up and wrote the algorithm. I got lucky and it ended up working. Using this table, I would have been more confident in my brute force algorithm. During competitions it'll save me time implementing an algorithm that is just good enough.

This tool predicted O(N2), which was the actual complexity of my solution! due to Lagrange's four-square theorem , which I did not know at the time. GoogleKickStart's expected solution was O(N1.5). What's great is that they left with a square root buffer for less performant solutions, but you might not have known that by looking directly at the problem statement.

Experiments

I went through a bunch of GoogleKickStart problems I solved and put in the time and input size to see what this tool estimates compared with Google's expected complexity, and my implementation's complexity. For Problem 1, Google usually gives you a large complexity buffer since they keep the input size small. In most cases, this tool estimates a larger complexity by a factor of O(N). This suggests that Google provides a smaller buffer that you can exploit with a less efficient solution, or this tool has huge room for improvement. For example, the tool suggests O(N3), but the max allowable is O(N2), like in 2020 Round G, Problem 2 "Maximum Coins". Finally, this tool doesn't handle multi-variate complexities, making some of the problems difficult to estimate, like in Google Kickstart 2018 Round H, Problem 1 "Big Buttons". In those cases I try my best to combine all the problems sizes into a single variable.
Problem Input Size Time Available Tool Estimate Reference Solution Complexity My Accepted Solution's Complexity Complexity Buffer of Estimate Error
Google Kickstart 2017 Round F, Problem 1 "Cake" 104 30 seconds O(N2) O(N1.5) O(N2) O(N0.5)
Google Kickstart 2018 Round F, Problem 1 "Common Anagrams" 101.70 20 seconds O(N4) O(N2) to O(N4) O(N2) O(1)
Google Kickstart 2020 Round B, Problem 1 "Bike Tour" 102 10 seconds O(N4) O(N) O(N) O(N3)
Google Kickstart 2020 Round H, Problem 1 "Retype" 109 20 seconds O(NlgN) O(N) O(N) O(lgN)
Google Kickstart 2018 Round E, Problem 3 "Yogurt" 103.70 20 seconds O(N3) O(N) to O(NlgN) O(NlgN) O(N2/lgN)
Google Kickstart 2018 Round H, Problem 1 "Big Buttons" 102 20 seconds O(N4) O(P2N) for simplicity O(N3) O(P2N) for simplicity O(N3) O(N)
Google Kickstart 2018 Round C, Problem 1 "Planet Distance" 103 20 seconds O(N3) O(N) O(N) O(N2)
Google Kickstart 2017 Round C, Problem 1 "Ambiguous Cipher" 101.70 20 seconds O(N4) O(N) O(N2) O(N3)
Google Kickstart 2020 Round G, Problem 2 "Maximum Coins" 103 20 seconds O(N3) O(N2) O(N2) O(N)
Google Kickstart 2020 Round B, Problem 2 "Bus Routes" 1012 20 seconds O(√D) O(N) to O(NlgD)) O(N) ?
Google Kickstart 2017 Round F, Problem 2 "Kicksort" 104 200 seconds O(N3) O(N) to O(N2) O(N2) O(N)

Bugs? Improvements?

Feel free to file an issue or a pull request.

Table Format for those without Javascript

Some people do not enable javascript in their browsers. As a result, the above tool to help figure out the runtime complexity will not work. So I put together the static table below for you to look up your target runtime complexity. Instead of the tool powered by javascript, it is powered by you searching the table.

How to use the table

Estimate the max complexity of your algorithm in order to achieve your deadline.
  1. Look for your how much time your algorithm has available in the Time column.
  2. In that row, look for your approximate problem size, expressed as a power of 2 or power of 10.
  3. The column you picked is the complexity of the algorithm you need to achieve to finish fast enough.

Pseudocode to calculate the table

  1. For each power p of 2 from 0 to 64
    1. For each runtime complexity f(n)
      1. Find the closest integer r such that f(2r) is closest to 2p
      2. Find the closest integer t such that f(10t) is closest to 2p

Using your own timings

Time how long it takes to count from 0 to 232 (or another power of 2 of your choosing) in milliseconds on your computer or in your language. Fill in the the textboxes and hit go. This will add a column scaled to your platform. (Needs javascript)
2
Time in milliseconds:

Powers of 2

O(lgN) O(√N) O(N) O(NlgN) O(N2) O(N3) O(N4) O(2N) O(N!) O(NN) Java Time* Javascript Time** Notable Usage Time it yourself***
21, 100 20, 100 20, 100 20, 100 20, 100 20, 100 20, 100 20, 100 20, 100 20, 100 600 ns ****
22, 101 22, 100 21, 100 21, 100 20, 100 20, 100 20, 100 20, 100 21, 100 20, 100 500 ns ****
24, 101 24, 101 22, 100 21, 100 21, 100 20, 100 20, 100 21, 100 21, 100 21, 100 500 ns ****
28, 102 26, 102 23, 101 22, 100 21, 100 21, 100 20, 100 21, 100 21, 100 21, 100 600 ns ****
216, 105 28, 102 24, 101 22, 100 22, 100 21, 100 21, 100 22, 100 22, 100 21, 100 1 μs, 0 ns ****
232, 1010 210, 103 25, 101 23, 101 22, 100 21, 100 21, 100 22, 100 22, 100 21, 100 1 μs, 400 ns ****
264, 1019 212, 103 26, 102 24, 101 23, 101 22, 100 21, 100 22, 100 22, 100 21, 100 2 μs, 400 ns ****
2128, 1039 214, 104 27, 102 25, 101 23, 101 22, 100 21, 100 22, 100 22, 100 21, 100 4 μs, 300 ns ****
2256, 1077 216, 105 28, 102 25, 101 24, 101 22, 100 22, 100 23, 100 22, 100 22, 100 8 μs, 0 ns ****
2512, 10154 218, 105 29, 102 26, 102 24, 101 23, 101 22, 100 23, 100 22, 100 22, 100 15 μs, 800 ns ****
2210, 10308 220, 106 210, 103 27, 102 25, 101 23, 101 22, 100 23, 101 22, 100 22, 100 33 μs, 700 ns ****
2211, 10616 222, 106 211, 103 28, 102 25, 101 23, 101 22, 100 23, 101 22, 100 22, 100 67 μs, 800 ns ****
2212, 101232 224, 107 212, 103 29, 102 26, 101 24, 101 23, 100 23, 101 22, 100 22, 100 188 μs, 800 ns ****
2213, 102464 226, 108 213, 104 210, 103 26, 102 24, 101 23, 101 23, 101 22, 100 22, 100 376 μs, 300 ns ****
2214, 104928 228, 108 214, 104 210, 103 27, 102 24, 101 23, 101 23, 101 22, 100 22, 100 469 μs, 600 ns ****
2215, 109856 230, 109 215, 104 211, 103 27, 102 25, 101 23, 101 23, 101 23, 100 22, 100 1 ms, 369 μs ****
2216, 1019712 232, 109 216, 105 212, 103 28, 102 25, 101 24, 101 24, 101 23, 100 22, 100 1 ms, 970 μs ****
2217, 1039424 234, 1010 217, 105 213, 104 28, 102 25, 101 24, 101 24, 101 23, 100 22, 100 756 μs, 500 ns ****
2218, 1078848 236, 1011 218, 105 214, 104 29, 102 26, 101 24, 101 24, 101 23, 100 22, 100 1 ms, 155 μs **** Efficient MD5 Collision calculation: 2013 Xie Tao, Fanbao Liu, and Dengguo Feng (2^18 time)
2219, 10157696 238, 1011 219, 105 215, 104 29, 103 26, 102 24, 101 24, 101 23, 100 22, 100 2 ms, 28 μs 1 ms, 0 μs
2220, 10315392 240, 1012 220, 106 216, 105 210, 103 26, 102 25, 101 24, 101 23, 100 22, 100 3 ms, 232 μs 1 ms, 0 μs A linear solution to the sorting question Eric Schmidt asked President Obama
2221, 10630784 242, 1013 221, 106 217, 105 210, 103 27, 102 25, 101 24, 101 23, 101 22, 100 6 ms, 568 μs 3 ms, 0 μs
2222, 101261568 244, 1013 222, 106 218, 105 211, 103 27, 102 25, 101 24, 101 23, 101 22, 100 12 ms, 983 μs 6 ms, 0 μs
2223, 102523136 246, 1014 223, 107 219, 105 211, 103 27, 102 25, 101 24, 101 23, 101 22, 100 9 ms, 183 μs 11 ms, 0 μs
2224, 105046272 248, 1014 224, 107 220, 106 212, 103 28, 102 26, 101 24, 101 23, 101 23, 100 17 ms, 314 μs 24 ms, 0 μs
2225, 1010092544 250, 1015 225, 107 221, 106 212, 103 28, 102 26, 101 24, 101 23, 101 23, 100 1 ms, 740 μs 51 ms, 0 μs
2226, 1020185088 252, 1016 226, 108 221, 106 213, 104 28, 102 26, 102 24, 101 23, 101 23, 100 3 ms, 459 μs 95 ms, 0 μs
2227, 1040370176 254, 1016 227, 108 222, 107 213, 104 29, 102 26, 102 24, 101 23, 101 23, 100 6 ms, 930 μs 197 ms, 0 μs
2228, 1080740352 256, 1017 228, 108 223, 107 214, 104 29, 102 27, 102 24, 101 23, 101 23, 100 14 ms, 258 μs 392 ms, 0 μs
2229, 10161480704 258, 1017 229, 108 224, 107 214, 104 29, 103 27, 102 24, 101 23, 101 23, 100 30 ms, 352 μs 776 ms, 0 μs
2230, 10322961408 260, 1018 230, 109 225, 107 215, 104 210, 103 27, 102 24, 101 23, 101 23, 100 58 ms, 379 μs 1 s, 560 ms
2231, 10645922816 262, 1019 231, 109 226, 108 215, 104 210, 103 27, 102 24, 101 23, 101 23, 100 131 ms, 277 μs 4 s, 723 ms
2232, 101291845632 264, 1019 232, 109 227, 108 216, 104 210, 103 28, 102 25, 101 23, 101 23, 100 250 ms, 475 μs 6 s, 46 ms
2233, 102583691264 266, 1020 233, 1010 228, 108 216, 105 211, 103 28, 102 25, 101 23, 101 23, 101 483 ms, 496 μs 12 s, 95 ms
2234, 105167382528 268, 1020 234, 1010 229, 109 217, 105 211, 103 28, 102 25, 101 23, 101 23, 101 923 ms, 904 μs 24 s, 830 ms
2235, 1010334765056 270, 1021 235, 1010 230, 109 217, 105 211, 103 28, 102 25, 101 23, 101 23, 101 1 s, 660 ms 48 s, 955 ms
2236, 1020669530112 272, 1022 236, 1011 231, 109 218, 105 212, 103 29, 102 25, 101 23, 101 23, 101 3 s, 303 ms 3 minutes, 15 s*****
2237, 1041339060224 274, 1022 237, 1011 232, 109 218, 105 212, 103 29, 102 25, 101 23, 101 23, 101 6 s, 576 ms 6 minutes, 31 s*****
2238, 1082678120448 276, 1023 238, 1011 233, 1010 219, 105 212, 103 29, 102 25, 101 23, 101 23, 101 13 s, 220 ms 13 minutes, 3 s*****
2239, 10165356240896 278, 1023 239, 1011 234, 1010 219, 106 213, 104 29, 103 25, 101 23, 101 23, 101 26 s, 429 ms 26 minutes, 6 s*****
2240, 10330712481792 280, 1024 240, 1012 235, 1010 220, 106 213, 104 210, 103 25, 101 23, 101 23, 101 52 s, 850 ms 52 minutes, 13 s*****
2241, 10661424963584 282, 1025 241, 1012 236, 1011 220, 106 213, 104 210, 103 25, 101 23, 101 23, 101 3 minutes, 31 s***** 1 hours, 44 minutes*****
2242, 101322849927168 284, 1025 242, 1012 237, 1011 221, 106 214, 104 210, 103 25, 101 23, 101 23, 101 7 minutes, 2 s***** 3 hours, 28 minutes*****
2243, 102645699854336 286, 1026 243, 1013 238, 1011 221, 106 214, 104 210, 103 25, 101 23, 101 23, 101 14 minutes, 5 s***** 6 hours, 57 minutes*****
2244, 105291399708672 288, 1026 244, 1013 239, 1011 222, 106 214, 104 211, 103 25, 101 24, 101 23, 101 28 minutes, 11 s***** 13 hours, 55 minutes***** 20 minutes to solve the Enigma code every morning.
2245, 1010582799417344 290, 1027 245, 1013 240, 1012 222, 106 215, 104 211, 103 25, 101 24, 101 23, 101 56 minutes, 22 s***** 1 days, 3 hours*****
2246, 1021165598834688 292, 1028 246, 1014 241, 1012 223, 107 215, 104 211, 103 25, 101 24, 101 23, 101 1 hours, 52 minutes***** 2 days, 7 hours*****
2247, 1042331197669376 294, 1028 247, 1014 242, 1012 223, 107 215, 104 211, 103 25, 101 24, 101 23, 101 3 hours, 45 minutes***** 4 days, 15 hours*****
2248, 1084662395338752 296, 1029 248, 1014 242, 1013 224, 107 216, 104 212, 103 25, 101 24, 101 23, 101 7 hours, 30 minutes***** 9 days, 6 hours*****
2249, 10169324790677504 298, 1029 249, 1015 243, 1013 224, 107 216, 105 212, 103 25, 101 24, 101 23, 101 15 hours, 1 minutes***** 18 days, 13 hours*****
2250, 10338649581355008 2100, 1030 250, 1015 244, 1013 225, 107 216, 105 212, 103 25, 101 24, 101 23, 101 1 days, 6 hours***** 37 days, 3 hours*****
2251, 10677299162710016 2102, 1031 251, 1015 245, 1013 225, 107 217, 105 212, 103 25, 101 24, 101 23, 101 2 days, 12 hours***** 74 days, 6 hours*****
2252, 101354598325420032 2104, 1031 252, 1015 246, 1014 226, 107 217, 105 213, 103 25, 101 24, 101 23, 101 5 days, 0 hours***** 148 days, 12 hours*****
2253, 102709196650840064 2106, 1032 253, 1016 247, 1014 226, 108 217, 105 213, 104 25, 101 24, 101 23, 101 10 days, 0 hours***** 297 days, 1 hours*****
2254, 105418393301680128 2108, 1032 254, 1016 248, 1014 227, 108 218, 105 213, 104 25, 101 24, 101 23, 101 20 days, 1 hours***** 1 years, 229 days*****
2255, 1010836786603360256 2110, 1033 255, 1016 249, 1015 227, 108 218, 105 213, 104 25, 101 24, 101 23, 101 40 days, 2 hours***** 3 years, 93 days*****
2256, 1021673573206720512 2112, 1034 256, 1017 250, 1015 228, 108 218, 105 214, 104 25, 101 24, 101 23, 101 80 days, 4 hours***** 6 years, 186 days***** brute force attack of DES is 2^56 in the worst case
2257, 1043347146413441024 2114, 1034 257, 1017 251, 1015 228, 108 219, 105 214, 104 25, 101 24, 101 23, 101 160 days, 8 hours***** 13 years, 8 days*****
2258, 1086694292826882048 2116, 1035 258, 1017 252, 1015 229, 108 219, 105 214, 104 25, 101 24, 101 23, 101 320 days, 16 hours***** 26 years, 16 days***** 303 days to calculate 50,000,000,000,000 digits of pi
2259, 10173388585653764096 2118, 1035 259, 1018 253, 1016 229, 109 219, 106 214, 104 25, 101 24, 101 23, 101 1 years, 276 days***** 52 years, 32 days*****
2260, 10346777171307528192 2120, 1036 260, 1018 254, 1016 230, 109 220, 106 215, 104 25, 101 24, 101 23, 101 3 years, 187 days***** 104 years, 64 days*****
2261, 10693554342615056384 2122, 1037 261, 1018 255, 1016 230, 109 220, 106 215, 104 25, 101 24, 101 23, 101 7 years, 10 days***** 208 years, 128 days*****
2262, 101387108685230112768 2124, 1037 262, 1018 256, 1017 231, 109 220, 106 215, 104 25, 101 24, 101 23, 101 14 years, 21 days***** 416 years, 257 days*****
2263, 102774217370460225536 2126, 1038 263, 1019 257, 1017 231, 109 221, 106 215, 104 25, 101 24, 101 23, 101 28 years, 42 days***** 833 years, 150 days*****
2264, 105548434740920451072 2128, 1038 264, 1019 258, 1017 232, 109 221, 106 216, 104 26, 100 24, 101 24, 101 56 years, 84 days***** 1666 years, 301 days***** 85,900 node Travelling Salesman problem was solved in 136 CPU Years.
*- ran using a loop that counts from 1 to 2^N on an AMD-FX6300
**- ran using a loop that counts from 1 to 2^N on an AMD-FX6300 in my Google Chrome 90.0.4430.93
*** - Counts from 1 to 2^N in your browser.
**** - I couldn't measure such a small time scale in the browser.
***** - These are estimated because I do not want to leave my computer running that long.