big O notation of this code

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");  
}

what can be the big-O notation of this code? my guess is N*(2^(logN))

I have assigned my hw already! this is just my pre-curiosity!

Answer 1

Looks linear to me. But your formatting is pretty screwed up, so it's hard to tell.

EDIT: Alright, recursion involved. Not linear, then. It would be easier if we had meaningful variable names.

Answer 2

ara is a recursive implementation of binary search. That is O(log n).

It is called 2n-1 times. Multiplying the two terms, the program as a whole is O(n log n).