Priority queues with binary priorities

K. Kalorkoti, D.H. Tulley

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a priority queue of unbounded capacity whose input is the sequence 1,2,…,n where each i is given a binary priority. We prove a previously conjectured recurrence for the number of allowable input–output pairs achievable by such a queue with z items of priority 0; the proof provides a new application of inseparable permutations. We then give upper and lower bounds for this and deduce that for fixed z the growth rate is O(n!logz(n)). We also study the total number of allowable input–output pairs where the number of items of priority 0 is not fixed and provide very tight upper and lower bounds which imply that the growth rate is O(nn!log(n)).
Original languageEnglish
Pages (from-to)133-144
Number of pages12
JournalTheoretical Computer Science
Volume262
Issue number1-2
DOIs
Publication statusPublished - Jul 2001

Fingerprint

Dive into the research topics of 'Priority queues with binary priorities'. Together they form a unique fingerprint.

Cite this