"Without Loss of Generality" In proofs, the phrase, "without loss of generality," abbreviated w.l.o.g., is frequently used. It means that we can assume something for purposes of the proof. Suppose that you are trying to prove a proposition P, and you say, "w.l.o.g. Q," where Q is some other proposition. You then mean that for purposes of the proof, you can assume Q is true; it does not mean that Q is true. More formally, it means that you have an easy proof (usually an extremely easy proof) that (Q -> P) -> P. Here is a simple example from this course. (Actually, almost all examples of the use of "w.l.o.g." are simple.) If rho is the request sequence for an instance of the paging problem, then, without loss of generality, rho has no consecutive requests to the same page. Clearly, in practice, there can be any number of consecutive requests to the same page. What we mean to say is that, for purposes of proving optimality or competitiveness, once we have a proof that works assuming no consecutive requests, we know that the same result also holds in all cases. The reason is that any request that is identical to the previous request is trivially served at zero cost, and both players know this, and both players know that both players know this. Therefore, that request does nothing to increase or decrease cost of either player, nor to change the knowledge of either player. The proper response of any offline or online algorithm to such a request is to do nothing, and forget that it ever happened. The "w.l.o.g." technique sometimes appears using other words. Here are some examples: "By symmetry, we can assume that ... " "Case 3 is similar to Case 1"