CODEWITHSUNDEEP
cbig-o
edib
edib

Reputation: 882

big O notation of this code

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!

Upvotes: 0

Views: 507

Answers (2)

ephemient
ephemient

Reputation: 204946

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).

Upvotes: 6

Anon.
Anon.

Reputation: 60033

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.

Upvotes: 0

Related Questions