上篇提到 input size 與 complexity 互為因果
而我們用f(n)來表示 complexity 與 input size 間的方程式(equation)關係

雖然是中文但是好像完全聽不懂？

the f(n) and the time complexity

每個 +-*/= (加 減 乘 除 等於)符號都視為一個 operation
當 operation 越多，complexity 則越大

寫一個用來打招呼的 function

function greeting(n){
    for(let i=0;i<=n;i++){
        console.log('hello');
    }
    console.log('hello');
    console.log('hello');
    console.log('hello');
}

當 greeting 的n=5 的時候，greeting 的 f(n)是多少呢？
來動手算看看...

答案是 9

for loop
let i=0;i<=n;i++ 要執行 5+1 次

外面的hello 出現3次
console.log('hello');

因此 f(n) = 6+3 = 9

那如果input size=n，f(n)又是？
把n帶入
n+1+3=n+4
也就是說，greeting 這個function的 n(input size) 與 complexity 為n+4 的關係
因此我們可以輕鬆的推斷出當 n 為各種數值時，對應 n 所執行的次數

那如果 input size 很大，大到極致的話，這個方程式還管用嗎？

concept of Big O notation

• Big O Notation is a tool to describe the asymptotic behavior of the alogorithm as the input size grows toward large or infinity.
• Big O Notation has the "worst case scenerio", which means it shows the general trends of complexity when the inputs is extremely large.

簡單來說就是，big O 就是當 algorithm 的 input size 變的超大甚至趨近無限的時候用來顯示最壞情況下 complexity 趨勢的工具，用 O(complexity) 表示

rule of big O Notation

1. Constant doesn't matter / 常數可忽略
   E.g f(n)= 3n ,O(n) (3 為常數，不因為n改變而改變 )
2. Small Terms don't matter
   E.g f(n)= n+99999, O(n)
3. Logarithm Base doesn't matter / log 底數可忽略不計
   E.g f(n)= log base 10 of n, O(log n)

exercise of O(n)

Q:
Given an algorithm that has time complexity f(n)=13n^3+6n+980, what's the big O of this algorithm?

A:O(n^3)

去掉 constant=13，去掉small terms=6n+980
留下 n^3=n*n*n 也就是 n 的三次方

Q:
Given an algorithm that has time complexity f(n)=68, what's the big O of this algorithm?

A:O(1)
Since the running time is constant, and the constant doesn't grow with n, so the complexity is O(1)

相關資源

Big O Notation Tutorial – A Guide to Big O Analysis
https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/