Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

sammyMaX's blog

By sammyMaX, history, 5 weeks ago, In English,

If you're interested in learning more about CPU hardware details and how they affect program performance, read my blog post here on how memory latency impacts binary search and causes an

$$$O(\sqrt[3]{n})$$$

runtime.

Enjoy!

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

»
5 weeks ago, # |
  Vote: I like it +60 Vote: I do not like it

Envying people living in $$$k$$$-dimensional space (of course,

$$$k > 3$$$

), where binary search takes just

$$$O(\sqrt[k]{n})$$$

time!
»
5 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

My whole life has been a lie.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it