CODEWITHSUNDEEP
algorithmtime-complexitybinary-search
krnactry
krnactry

Reputation: 57

Time complexity for n-ary search.

I am studying time complexity for binary search, ternary search and k-ary search in N elements and have come up with its respective asymptotic worse case run- time. However, I started to wonder what would happen if I divide N elements into n ranges (or aka n-ary search in n elements). Would that be a sorted linear search in an array which would result in a run-time of O(N)? This is a little confusing. Please help me out!

Upvotes: 3

Views: 5224

Answers (1)

user1952500
user1952500

Reputation: 6781

What you say is right.

For a k-ary search we have:

  1. Do k-1 checks in boundaries to isolate one of the k ranges.
  2. Jump into the range obtained from above.

Hence the time complexity is essentially O((k-1)*log_k(N)) where log_k(N) means 'log(N) to base k'. This has a minimum when k=2.

If k = N, the time complexity will be: O((N-1) * log_N(N)) = O(N-1) = O(N), which is the same algorithmically and complexity-wise as linear search.

Translated to the algorithm above, it is:

  1. Do N-1 checks in boundaries (each of the first N-1 elements) to isolate one of the N ranges. This is the same as a linear search in the first N-1 elements.
  2. Jump into the range obtained from above. This is the same as checking the last element (in constant time).

Upvotes: 4

Related Questions