Mirror of forum.nim-lang.org

6126 :: upperBound/lowerBound in algorithm O(log n) or O(n) ?

• peheje (orginal) [2020-03-27T22:38:29+01:00] view original

  Hi

  In Java binary search returns a negative index if target not found in array where negative index is where to insert (as positive) to preserve sorted array.

  Is upperBound/lowerBound following binary search speeds O(log n) worst case or linearly?

  I'm too stupid to read the source code:

  https://github.com/nim-lang/Nim/blob/version-1-0/lib/pure/algorithm.nim#L281

  I'm guessing the shr 1 is dividing by 2 so it would be O(log n)?

  Btw. the documentation on Sort and IsSorted specifies worst case as O notation, could be nice to add for others as well if possible.

  Cheers

---

• treeform (orginal) [2020-03-27T23:22:07+01:00] view original

  Yes shr 1 is divide by 2. It looks like the function does what you would except at O(log n). But...

  The O(log n) stuff works in theory, but in practice memory access and cache hotness have bigger

  impact on performance. I don't think it's that useful to specify this.

  http://www.brendangregg.com/blog/2017-05-09/cpu-utilization-is-wrong.html

  Always measure!

  The main thing I like about Nim is that I can always make some thing faster... there are no limits.

  But you got to measure!

---

• peheje (orginal) [2020-03-28T11:15:50+01:00] view original

  Thank you treeform. Have a nice weekend.

---