viola89
March 3rd, 2009, 02:08 PM
Hi, can someone please help with this: We are given an array of n bits, and we want to determine if it contains two consecutive zero bits. Show that when n mod 3 = 0 or 2, we must examine every bit in the array.
that is, give an adversary strategy that forces any algorithm to examine every bit when n = 2, 3, 5
thank you
that is, give an adversary strategy that forces any algorithm to examine every bit when n = 2, 3, 5
thank you