Binary Search - Time Complexity

Time Complexity of Binary Search Algorithm





Algorithm:

 

    Int BinarySearch(int Array[], int value, int left, int right){

               Int mid=(left+right)/2

 

 

If(Array[mid]== value){

Return mid;

}elif(left>right){

Return -1;

}elif(Array[mid] > value){

BinarySearch(Array,left,mid-1);

}else{

 

BinarySearch(Array, mid+1,right);

}

 

End if

 

}






Let N be the Size of the Binary tree

 

T(N) =  C +  T(N/2)   ------ 1

T(N/2) = C + T (N/4) ------2


Substitute 2 à 1

T(N) = 2C + T(N/4)    -------3

T(N/4) = C + T(N/8)  --------4



Substitute 4 à 3

 

T(N) = 3C + T(N/8) ------5

 

pattern

 

T(N) = iC + T(N/2i)       where I is an integer

 

 

At some point , as N/2i diminishes , we reach only 1 element,

 

So        

                 T(N) = T(1)

                  T(N)= T(N/2i) + iC   --------6

 

à   N/2i  = 1

è  N = 2i

 

 

 

Take log2 on both sides

 

log2 N = log2 2i

log2 N = i  ---------7

 

Substitute 7 à 6

 

T(N) = T(N/2 log2N) + C log2 N

T(N) = T(N/N) + C log2 N

T(N) = T(1) + C log2 N

Since T(1) is a constant value,


T(N) = K + C log2 N


To find the time complexity we need to remove constants,

 

Time complexity = T(N) = O(log2 N)

 

F(N) = O(log2 N)

Location: Balangoda, Sri Lanka

Comments

Post a Comment

Popular posts from this blog

Insertion Sort - Time Complexity

Image
 Time Complexity of Insertion Sort Selection Sort is using two for loops to do one iteration. The first loop (Outer loop ) travels through an array starting from index 0, while the inner loop runs from index i+1 to index less than i. The following diagram shows the Number of execution rounds it performs. when i is 0,, j is 1,  the inner for loop runs n-1 time. when i is 1, j is 2, the inner for loop runs n-2 times. Likewise, when i is n, j is n+1,  the inner for loop runs n times. So the total number of Execution rounds can be calculated by adding all Execution times in each i values.  Time Complexity =    n-1 (n-1)                                              2            ...
Read more

Selection Sort - Time Complextity

Image
  Time Complexity of Selection Sort  Selection sort  is using two for loops to do one iteration. The first loop (Outer loop ) travels through an array starting from index 1, while the inner loop runs from index 1 to index i-1. The following diagram shows the Number of execution rounds it performs. when i is 1, the inner for loop runs only one time. when i is 2, inner for loop runs 2 times. Likewise when i is   n   the inner for loop runs n times. So the total number of Execution rounds can be calculated by adding all Execution times in each i values.     Time Complexity       =    n (n+1)                                         2                     ...
Read more

Quick Sort - Time Complexity

Image
 Time Complexity of Quick Sort Algorithm:                            QuickSort(left, right){                                   If(left < right){                                              Pi= partition(left,right)                                                QuickSort(left,pi)                                         ...
Read more