O(n) 函数

当输入变得非常大时，O(n) 的函数会线性增加操作数。作为 O(n) 的函数的简单示例是线性搜索算法，其针对输入的大小运行一次。

以下伪代码将是 O(n)，因为它总是被输入大小限制在上面，因为算法永远不会比输入大小运行更多倍。

function LinearSearch (SearchArray, SearchFor)
    for each element in SearchArray
        if the element is SearchFor
            return the index of element