The expected saving on the specified successful searches is
(1)
which tends to one iteration as increases. The fractional saving is , which tends to zero. Both versions have logarithmic expected time, and the improvement is a bounded average saving rather than a change of growth rate. A target at the first middle position benefits greatly, but the uniform distribution does not concentrate on that event. The extra equality branch and machine-level costs also matter when comparing measured execution times.
Figure 1.
Early equality return saves less than one iteration on average in perfect search arrays
. Original exact iteration counts and their difference for uniformly chosen present targets in arrays of length . The curves describe loop iterations, not measured execution time. Details.

Ancestors (11)

  1. 2
  2. Imperative programming (resit)
  3. 2021
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version