2.1 Time complexity

Constant time

Linear time

Quadratic time

$$ O(1) $$

The Big O notation for constant time is O(1).

Logrithmic time

$$ O(log n) $$

The Big O notation for logrithmic time is O(log n).

$$ O(n) $$

The Big O notation for linear time is O(n).

Quasilinear time

$$ O(nlog n) $$

The Big O notation for quasilinear time is O(nlog n).

Swift 中 sort 方法的时间复杂度。

$$ O(n^2) $$

The Big O notation for quadratic time is O(n^2).

Polynomial time

多项式

Exponential time

指数

Factorial time

阶乘

2.3 Other notations

Big Omega

best-case runtime

Big Theta

the same best and worse case