这段代码的大O表示法

Question

int ara(int dizi[], int ilk, int son, int deger) { 
      int indeks;    
      if ( ilk > son ) 
        return 0; 

      indeks = (ilk + son) / 2; 
      if ( dizi[indeks] < deger ) 
        return ara(dizi, indeks+1, son, deger); 
       else if ( dizi[indeks] > deger ) 
        return ara(dizi, ilk, indeks-1, deger); 
       else  
       return 1; 
} 

for (i=1; i<2*n; i++)   { 
    printf("Bir sayi giriniz: "); 
    scanf("%d", &sayi); 
    sonuc = ara(matrix, 0, n-1, sayi); 
    if ( sonuc == 1 ) 
      printf("Found!\n"); 
     else 
      printf("Not Found!\n");  
}

什么可以是这段代码的大O符号？我猜是N*(2 ^(logN))

我已经分配了我的hw!这只是我的好奇心!

Answer 1

ara是二进制搜索的递归实现.那是O(log n).

它被称为2n-1次.将这两个项相乘,程序整体为O(n log n).