问题的复杂性由其最优算法决定，而非某个具体解

一个问题本身”有多复杂”，不能简单地等同于”我手头这个解法有多复杂”——同一个问题可能有多个不同效率的解法，其中必有一个最优。因此一个问题的（时间）复杂性被严格定义为解决它的最优算法的复杂性：排序问题的复杂性是 Θ(n log₂n)，因为归并排序（属于这一类）已被证明是最优解，尽管插入排序（属于更慢的 Θ(n²)）也能解决同一个问题。当我们还不确定某个算法是否已经是最优解时，就用大 O 记号表示”至少不会比这更差”的上限估计，而不是精确等号。发散：这个定义提醒我们，判断一个问题”难不难”，不能只看你自己想出的那个解法效率如何——除非能证明这已经是理论上的最优解，否则一个看起来很慢的问题完全可能存在一个尚未被发现的高效算法，”问题的复杂性”和”你已知算法的复杂性”是两个概念，混淆二者是算法分析里最容易踩的认知陷阱。