complexité Temps d'une fonction Big-O

Question

J'essaie de trouver la complexité temporelle de cette fonction:

int bin_search(int a[], int n, int x); // Binary search on an array with size n. 

int f(int a[], int n) { 
    int i = 1, x = 1; 
    while (i < n) { 
     if (bin_search(a, i, x) >= 0) { 
      return x; 
     } 
     i *= 2; 
     x *= 2; 
    } 
    return 0; 
} 

La réponse est (log n)^2. Comment venir?
Le meilleur que je pouvais obtenir est log n. D'abord le i est 1, donc le temps sera couru log n fois.
Lors de la première interaction, lorsque i=1, la recherche binaire aura une seule interaction car la taille du tableau est 1 (i). Puis, quand i=2, deux interactions, et ainsi de suite jusqu'à ce que ce soit log n interactions.
Donc, la formule que je pensais tenir est this.
La somme est pour le moment et l'équation interne est parce que pour i=1 c'est log(1), pour i=2 c'est log(2) et ainsi de suite jusqu'à ce que ce soit log(n) à la fin.

Où est-ce que je me trompe?

Answer 1

Chaque itération effectue une recherche binaire sur les premiers éléments 2^i du tableau.

Vous pouvez calculer le nombre d'opérations (comparaisons):

log2(1) + log2(2) + log2(4) + ... + log2(2^m) 

log(2^n) égal n, donc cette série en simplifie:

0 + 1 + 2 + ... + m 

Où m est floor(log2(n)).

La série évalue à m * (m + 1)/2, en remplacement m nous obtenons

floor(log2(n)) * (floor(log2(n)) + 1)/2 

-> 0.5 * floor(log2(n))^2 + 0.5 * floor(log2(n)) 

Le premier élément domine la seconde, d'où la complexité est O(log(n)^2)