Unique ID.
The government of India has issued approximately 1171000000 Unique Identity cards to citizens (1.171 billion) until now. A unique id card (Aadhar) card is 12 digits long. When a new application arrives , a new ID is generated, the Computer Scientist in charge has to check if the ID to be alloted already exists. He could design a search to identify if the new ID generated randomly is unique in x number of searches(Best case) and in y number of searches(worst case).
- 1171000000
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The complexity of two types of searches are Linear search : Best case complexity O(1) , Worst Case complexity is O(N) Binary search : Best case complexity is O(1) , Worst case complexity is O(log N) where log(N) refers to log2(N).(Base 2). The best case complexity of 1 would occur when the new id already exists as the first element of the existing array of UIDs. It is well known now that a Binary Search can identify the number/string being searched in an array of N elements in log2(N) iterations which is much lower than a Linear search which takes N number of iterations. Only that a Binary search requires the array elements to be sorted. Going by this log2(1171000000) is 30.12509393 and so one would require 31 comparisons (worst case) or iterations to determine if an id already exists in the array of N elements. The best case as already discussed would be 1.