Packet scheduling is an important mechanism to provide QoS guarantees
in data networks.  A scheduling algorithm generally consists of two
functions: one estimates how the GPS (General Processor Sharing) clock
progresses with respect to the real time; the other decides the order
of serving packets based on an estimation of their GPS start/finish
times.  In this work, we answer important open questions concerning
the computational complexity of performing the first function. We
systematically study the complexity of computing the GPS virtual
start/finish times of the packets, which has long been believed to be
$\Omega(n)$ per packet but has never been either proved or refuted.
We also answer several other related questions such as ``whether the
complexity can be lower if the only thing that needs to be computed is
the relative order of the GPS finish times of the packets rather than
their exact values?''