complexity of bineary search
we know that complexity of binary search= O(logn) because going from n to n/2 to n/4 to 1 takes logn steps
actually, i was trying to calculate it from a different way. Below is that way:
T(n)=2T(n/2)+1 // time taken for search of n elements is equal to sum of time taken to search n/2 and n/2 elements + 1 unit time for comparison of element
so, T(n)=2(2T(n/4)+2+1
so, T(n)=(22)T(n/22)+21+20
so, T(n)=(2i)T(n/2i)+2i-1+....+20
taking boundary condition T(1)=1 //because if there is just one element..the time taken is 1 unit for only comparison
solving above two equations,
we get T(n)=2n-1 which is not equal to logn...now why is this so??
actually, i was trying to calculate it from a different way. Below is that way:
T(n)=2T(n/2)+1 // time taken for search of n elements is equal to sum of time taken to search n/2 and n/2 elements + 1 unit time for comparison of element
so, T(n)=2(2T(n/4)+2+1
so, T(n)=(22)T(n/22)+21+20
so, T(n)=(2i)T(n/2i)+2i-1+....+20
taking boundary condition T(1)=1 //because if there is just one element..the time taken is 1 unit for only comparison
solving above two equations,
we get T(n)=2n-1 which is not equal to logn...now why is this so??
I don't understand why did you put 2T(n/2).
You test only `one' of the halves, according if the number is greater or lesser.
Those checks take a `C' time, and that's why the total is T(n) = C + T(n/2)
You test only `one' of the halves, according if the number is greater or lesser.
Those checks take a `C' time, and that's why the total is T(n) = C + T(n/2)
Topic archived. No new replies allowed.