On 18/05/2017 11:57, Martin Ward wrote:
The "random bit probe" algorithm is an example of
a "coupon collector's problem":
https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
The expected number of trials (and therefore runtime)
is n log n (plus smaller terms). This might still
take too long on a mainframe of the era we are talking about,
given that it took over two seconds on a modern PC.
Also: for those who worry about such things, the "worst case runtime"
is infinite :-)
--
Martin
Dr Martin Ward STRL Principal Lecturer & Reader in Software Engineering
[email protected] http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Mirrors: http://www.gkc.org.uk and http://www.gkc.org.uk/gkc
