Find the time complexity of Binary Search Algorithm.
Time complexity of binary search
In binary search each step of the algorithm divides the list of items being searched in half of the list.
So we can say that
T(n)= T(n/2) +1 where n>1
= T(n/4) +1 +1
= T(n/22) + 2
= T(n/23) +3
……………..
………………
=T(n/2k) + k
If n=2k then k= log2n
= T(1) + log2n
So
T(n)= O(log2n)
Best case condition occur when the element to be searched in first time. Then complexity is O(1).
a) Sort the following list using the Radix Sort :
189, 205, 986, 421, 97, 192, 535, 839, 562, 674
Write a C program to find factorial(using recursion) of any no.
What is a Judy array?
Distinguish between Decision table versus decision tree
Write a C program to find a number is AMSTRONG or NOT.
