Data Structures and Algorithm Analysis Notes 中的文章
• [Lecture 1] Introduction, Mathematics Review, Recursion
• [Lecture 2] Asymptotic Notation, Algorithm Analysis
• 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

[Lecture 2] Asymptotic Notation, Algorithm Analysis

1. Asymptotic Notation

1.1 Definitions

Here are some definitions to demonstrate the value trend of a function when the input N grows up .

The big-O notation $O$ defines a class of functions that have the same attribution :

$T\left(N\right)=O\left(f\left(N\right)\right)$ if there are positive constants $c$ and ${n}_{0}$ such that $T\left(N\right)\le cf\left(N\right)$ when $N\ge {n}_{0}$.

Note that 「$=$」 here is not a tradition symbol 「equal」, which describes $T\left(N\right)$ belongs to a set of functions satisfied with the requirement above.

$O\left(f\left(N$