Там 2 очереди: 1 активная, 1 истекшая.
Так вот, когда квант времени процесса истекает, то для него пересчитывается значения кванта (и приоритета). Затем он помещается в очередь истекших.
В итоге, шедулер просто переставляет указатели массивов местами: для истекших и активных.
Но ведь число пересчетов равно числу всех процессов в худшем случае, т.е. за линейное время. Где тут O(1)?