Online Interview Training Site
Posted on
6
Aug
2009 - by
Bishal-Nath In:
Algorithm Basics
What do u meant by logn order of complexity? What is the base of logn complexity? Is the base constant for the entire algorithm that gives logn complexity
logn complexity comes when the problem can be divided into sub problem and each problem can be again divided into sub problem till it becomes under control to solve by looking into it.
The base of the log is taken from the way the problem is divided. If the problem can be divided exactly into two sub problem and then again two then the base will be 2. If the problem can be divided into 3/2(1/3 and 2/3 each time) then the base will be 3/2.