In binary search if all elements are same .In that case the time complexity of Binary search will be O(N)

Question

 Basically the time complexity of Binary Search is O(log N).
    What if all the elements are same.
    
    In the bottleneck step. 
    Assuming all the values in the array are the same, we get the following relation :

 T(N) = 2 * T(N/2) + constant
    = 4 * T(N/4) + constant ( 2 * constant = another constant )
    = 8 * T(N/8) + constant
    …
    = N * T(N/N) + constant
    = N + constant
    = O(N)

In that case the time complexity of Binary search will be O(N).

question from:https://stackoverflow.com/questions/65909473/in-binary-search-if-all-elements-are-same-in-that-case-the-time-complexity-of-b

Answer 1

Waitting for answers