Worst Case-Zeit Komplexität für den Code

Question

Warum ist die ungünstigste Zeit Komplexität des folgenden Codes O (N)?

/* 
* V is sorted 
* V.size() = N 
* The function is initially called as searchNumOccurrence(V, k, 0, N-1) 
*/ 

int searchNumOccurrence(vector<int> &V, int k, int start, int end) { 
    if (start > end) return 0; 
    int mid = (start + end)/2; 
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); 
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); 
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 
} 

Answer 1

Was ist der schlimmste Fall? der schlimmste Fall wird sein, dass alle Elemente gleich sind und gleich k sind. Dann müssen Sie mindestens alle Elemente lesen, nämlich N. Da die meisten Funktionsaufrufe die Ausgabe um 1 erhöhen, gibt es etwa N Funktionsaufrufe (einige geben 0 zurück, aber sie erzeugen keine neuen Aufrufe). Daher ist die komplexeste Zeit O(N).

Answer 2

Ja, im schlimmsten Fall, wenn alle Zahlen im Array gleich k ist, dann in diesem schlimmsten Fall wird die Rekursion sein:

T(n) = 2*T(n/2) 

Die in O(n) übersetzt.