On finding a chain decomposition of a Partial Order
Your access to $A$ (which is $P$ in the paper) is through an oracle, and you're charged for each query. But in terms of the query count, your accesses to $A&#39;$ (which is $P&#39;$ in the paper and is an "induced sub-poset" of $A$) are free. So the answer is that a chain decomposition of $A&#39;$ is built without asking any new queries to $A$, only based on the relations in $A&#39;$, which are already known. Then a new element is inserted by performing a binary search on each chain of the chain decomposition, and this is where $w\log n$ queries are performed. 

Note that Theorem 6 relates to Figure 2 and not Figure 1. There the number of queries is decreased by querying asymptotically optimally, rather than blindly doing a binary search independently on each chain (which would ignore relations going between chains).