Question

JAVA What is the running time required for repeatedly splitting a problem into two equally sized halves, assuming no additional work needs to be done?

O(1)

O(log10N)

O(log2N)

O(log2N)

O(N)

O(N log N)

O(N2)

O(N3)

O(Nk)

O(2N)

O(N!)

Answer 1

O(log2N)

Step-by-step explanation:

Whenever there is repeated division or split of a problem in two equally sized halves an there is no additional work means there no work other than splitting the problem the time complexity is O(log2N).

You can take the example of binary search.It is an algorithm based on divide and Conquer.It divides the array in two equal halves on each iteration and it's worst case time complexity is O(logN).