sammyMaX's blog

Binary search takes cube root n time
By sammyMaX, history, 5 years 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
  • +97
  • Vote: I do not like it

»
5 years 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!

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

My whole life has been a lie.

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

→ Reply