Why does log(N) appear so frequently in Complexity Analysis?
117.8 هزار بار بازدید -
7 سال پیش
-
The term log(N) is often
The term log(N) is often seen during complexity analysis. This stands for logarithm of N, and is frequently seen in the time complexity of algorithms like binary search and sorting algorithms.
We show that log(N) is the minimum number of bits to uniquely define a number in the range 0 to N-1. We then argue that the minimum number of operations to search for a number in an array would also be log(N).
Finally, the reasoning is extended to sorting algorithms, where logN defines time required to find the appropriate index for a given element from the unsorted array to the sorted array.
Order complexity video: What is Time Complexity Analysis? - B...
Questions on the same topic:
https://stackoverflow.com/questions/9...
https://stackoverflow.com/questions/2...
https://goo.gl/xY6wXd
Keep in touch!
Facebook: gkcs0
https://www.quora.com/profile/Gaurav-...
https://github.com/gkcs/Competitive-P...
Contribute subtitles:
http://www.youtube.com/timedtext_cs_p...
We show that log(N) is the minimum number of bits to uniquely define a number in the range 0 to N-1. We then argue that the minimum number of operations to search for a number in an array would also be log(N).
Finally, the reasoning is extended to sorting algorithms, where logN defines time required to find the appropriate index for a given element from the unsorted array to the sorted array.
Order complexity video: What is Time Complexity Analysis? - B...
Questions on the same topic:
https://stackoverflow.com/questions/9...
https://stackoverflow.com/questions/2...
https://goo.gl/xY6wXd
Keep in touch!
Facebook: gkcs0
https://www.quora.com/profile/Gaurav-...
https://github.com/gkcs/Competitive-P...
Contribute subtitles:
http://www.youtube.com/timedtext_cs_p...
7 سال پیش
در تاریخ 1396/11/07 منتشر شده
است.
117,805
بـار بازدید شده