如何系統地確定函數的big-O？

Question

他們是否有條不紊的方式來做到這一點？就像如果給我這樣的功能：

public static int f2(int[] arr, int lo, int hi) 
{ 
    // N = initial value of (hi-lo+1) of 1st activation of f2 
    if(lo == hi) 
     return lo; 
    if(arr[hi] >= arr[lo]) 
     return f2(arr, lo+1, hi); 
    return f2(arr, lo, hi-1); 
} 

許多我已經看過了資源的不告訴你一步一步如何得到你從來沒見過一個函數的符號。有沒有辦法直觀地做到這一點？如果是這樣，我將如何以big-O的方式獲得最糟糕的運行時間？謝謝。

Answer 1

這是O（n），其中n是hi - lo + 1並且在每個遞歸由1

lo和hi減小之間的間隙我懷疑這是不可能的一般解決這個作爲最壞的情況是一樣的嘗試解決Halting problem。