竞争比

在输入顺序均匀随机的假设下，秘书问题的经典策略（先拒绝前n/e个候选人，之后选择第一个优于此前所有候选人的申请者）的竞争比约为1/e≈0.368，即至少能以37%的概率选中最佳候选人，且该比例是最优的。

竞争比定义为在线算法在最坏输入序列上的成本与最优离线算法成本之比的最大值。

页面调度问题已知的紧上下界与真实笔记本电脑的低缓存缺失率相去甚远。