资源消耗必须联系输入规模
时间复杂度通常计量基本计算步骤，空间复杂度计量计算所需的存储资源。它们被写成输入规模的函数，而不是某次运行的秒数或内存读数。算法分析考察某个方法的成本；问题的复杂度则涉及所有可用算法能够达到的资源界限，两者不能混为一谈。
输入规模取决于编码。一个整数的二进制位数与其数值并不相同：表示 1024 只需 11 位，而循环 1024 次已经远多于 11 次。因此宣称某算法随“数字大小”线性增长时，必须说明指的是数值还是输入长度。
最坏与平均回答不同问题
最坏情形分析针对同样规模的所有输入，给出资源消耗的最大值或适用上界。它提供保证，但不表示每个输入都达到这个代价。平均情形分析计算某种输入概率分布下的期望成本；没有说明分布，就不能把“平均”当成无需条件的事实。
例如从头依次查找一个无序列表中的目标，目标位于第一项时只需比较一次，位于最后一项时需比较全部 n 项。若保证目标存在且各位置等可能，平均比较次数是 (n+1)/2；若目标通常不在列表中，这个平均值就不再适用。最坏情况和真实负载都值得检查。
参考：[2]
增长率、上界与模型
渐近分析着重比较大规模输入时的增长趋势。O(n²) 表示一个渐近上界，不是恰好执行 n² 步，也不自动说明这是最紧的界。常数因子和较低阶项可能在小规模输入上占主导，因此增长阶较好的方法并不保证每次实测都更快。
计步还依赖模型。图灵机的单纸带与多纸带模型在可计算性上等价，但同一问题可能有不同的时间界。讨论复杂度时需要明确允许哪些基本操作，不能把处理任意长度整数的一次运算默认视为固定代价，再与逐位计费的模型直接比较。
能结束不代表能实用
一个穷举算法可能保证终止，却需要难以承受的时间。计算复杂性研究在可判定性之外进一步分类，例如 P 包含可以由确定模型在多项式时间内判定的问题。这个理论分类有稳定性和比较价值，但不是对现实运行时间的绝对承诺。
NP 的“是”实例有长度受输入规模多项式限制、能在多项式时间内验证的证书；“否”实例则没有能通过验证的证书。SAT 中的证书是使布尔公式为真的变量赋值。SAT 是 NP 完全问题：NP 中任何问题都可在多项式时间内归约到它，因此若 SAT 有多项式时间判定算法，就有 P=NP。这个问题至今未解；NP 完全性并不等于已证明必须指数时间，也不等于不可判定。
很大的多项式次数或常数仍可能使算法不实用；某些最坏情形很难的问题，也可能在特定输入集合上容易处理。证明一个具体算法慢，不等于证明问题的所有算法都慢。实际选择方法时，还需结合输入结构、规模、精确度需求及测量结果，区分已证明的下界与目前只知道的上界。