Show that n = O(nlogn) in data base
Answers
It generally means that any specific operation you apply to that data structure (like insertion/deletion/searching) would take logarithmic time i.e. each time the number or size of input would be reduced to half of its previous value.
Let’s take an example of binary search : -
You are given an array of 10 numbers like - 1,2,3,4,5,6,7,8,9,10.
Let’s say we need to search for 9 in this array. We start with the middle element of the array i.e. 5 and check whether our number is greater than or smaller than the middle element. Since 9>5, our new array would contain all the values greater than 5 since we don’t need numbers lesser than 5.
New array would be like - 6,7,8,9,10.
Applying the same procedure above and taking 8 as middle element, our new array would be like - 9,10.
Now in the next step, we would find our number 9 since there are only 2 numbers left.
So, rather than going all the way from 1 to 9 (Linear Search), we reduced our search space at each step into half in order to find our element. This kind of time complexity where at each step our input is reduced to half is known as O(logn) time.