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