Originally Posted by
razzle
In the definition of NEXTWHITE(i) it should be "j>i" right?
I'll assume that and make a suggestion for the (a) question.
In addition to the X[1::n] array you need a binary search tree where all indexes corresponding to a 0 in X are stored in sorted order. Lets call it BST. Initially BST holds all indexes between 1 and n (because all index positions of X are initially set to 0).
Now for LOCKUP(i) you use X. That takes O(1).
For BLACKEN(i) you set the corresponding bit in X which takes O(1), but you also remove the i index from BST (because it no longer corresponds to a 0) and that takes O(log n). All in all that's O(log n).
Finally for NEXTWHITE(i) you make a search in BST for the smallest index bigger than i. That will be j and it takes O(log n) to find it. (If i is in BST, j is its next bigger neighbour. If i is not in BST, j is where i should be if it were in BST).
So with BST in addition to X you get LOCKUP in O(1) and BLACKEN and NEXTWHITE in O(log n) which was requested in (a).