What does O log n mean exactly

Question

I am learning about Big O Notation running times and amortized times   I understand the notion of O n  linear time  meaning that the size of the input affects the growth of the algorithm proportionally   and the same goes for  for example  quadratic time O n2  etc  even algorithms  such as permutation generators  with O n   times  that grow by factorials   For example  the following function is O n  because the algorithm grows in proportion to its input n   f int n      int i    for  i   0  i  lt  n    i      printf   d   i       Similarly  if there was a nested loop  the time would be O n2    But what exactly is O log n    For example  what does it mean to say that the height of a complete binary tree is O log n    I do know  maybe not in great detail  what Logarithm is  in the sense that   log10 100   2  but I cannot understand how to identify a function with a logarithmic time

User · Answer

These 2 cases will  take O log n  time  case 1  f int n          int i        for  i   1  i  lt  n  i i 2          printf   d   i            case 2    f int n          int i        for  i   n  i gt  1   i i 2          printf   d   i

User · Answer

The explanation below is using the case of a fully balanced binary tree to help you understand how we get logarithmic time complexity    Binary tree is a case where a problem of size n is divided into sub-problem of size n 2 until we reach a problem of size 1     And that s how you get O log n  which is the amount of work that needs to be done on the above tree to reach a solution    A common algorithm with O log n  time complexity is Binary Search whose recursive relation is T n 2    O 1  i e  at every subsequent level of the tree you divide problem into half and do constant amount of additional work

User · Answer

I cannot understand how to identify a function with a log time    The most common attributes of logarithmic running-time function are that    the choice of the next element on which to perform some action is one of several possibilities  and only one will need to be chosen    or   the elements on which the action is performed are digits of n   This is why  for example  looking up people in a phone book is O log n   You don t need to check every person in the phone book to find the right one  instead  you can simply divide-and-conquer by looking based on where their name is alphabetically  and in every section you only need to explore a subset of each section before you eventually find someone s phone number   Of course  a bigger phone book will still take you a longer time  but it won t grow as quickly as the proportional increase in the additional size     We can expand the phone book example to compare other kinds of operations and their running time  We will assume our phone book has businesses  the  Yellow Pages   which have unique names and people  the  White Pages   which may not have unique names  A phone number is assigned to at most one person or business  We will also assume that it takes constant time to flip to a specific page   Here are the running times of some operations we might perform on the phone book  from fastest to slowest    O 1   in the worst case   Given the page that a business s name is on and the business name  find the phone number  O 1   in the average case   Given the page that a person s name is on and their name  find the phone number  O log n   Given a person s name  find the phone number by picking a random point about halfway through the part of the book you haven t searched yet  then checking to see whether the person s name is at that point  Then repeat the process about halfway through the part of the book where the person s name lies   This is a binary search for a person s name   O n   Find all people whose phone numbers contain the digit  5   O n   Given a phone number  find the person or business with that number  O n log n   There was a mix-up at the printer s office  and our phone book had all its pages inserted in a random order  Fix the ordering so that it s correct by looking at the first name on each page and then putting that page in the appropriate spot in a new  empty phone book    For the below examples  we re now at the printer s office  Phone books are waiting to be mailed to each resident or business  and there s a sticker on each phone book identifying where it should be mailed to  Every person or business gets one phone book    O n log n   We want to personalize the phone book  so we re going to find each person or business s name in their designated copy  then circle their name in the book and write a short thank-you note for their patronage  O n2   A mistake occurred at the office  and every entry in each of the phone books has an extra  0  at the end of the phone number  Take some white-out and remove each zero  O n  middot  n    We re ready to load the phonebooks onto the shipping dock  Unfortunately  the robot that was supposed to load the books has gone haywire  it s putting the books onto the truck in a random order  Even worse  it loads all the books onto the truck  then checks to see if they re in the right order  and if not  it unloads them and starts over   This is the dreaded bogo sort   O nn   You fix the robot so that it s loading things correctly  The next day  one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems  Every time the robot goes to load an original book  the factory printer makes a duplicate run of all the phonebooks  Fortunately  the robot s bug-detection systems are sophisticated enough that the robot doesn t try printing even more copies when it encounters a duplicate book for loading  but it still has to load every original and duplicate book that s been printed

User · Answer

If you are looking for a intuition based answer I would like to put up two interpretations for you    Imagine a very high hill with a very broad base as well  To reach the top of the hill there are two ways  one is a dedicated pathway going spirally around the hill reaching at the top  the other  small terrace like carvings cut out to provide a staircase  Now if the first way is reaching in linear time O n   the second one is O log n   Imagine an algorithm  which accepts an integer  n as input and completes in time proportional to n then it is O n  or theta n  but if it runs in time proportion to the number of digits or the number of bits in the binary representation on number then the algorithm runs in O log n  or theta log n  time

User · Answer

I would like to add that the height of the tree is the length of the longest path from the root to a leaf  and that the height of a node is the length of the longest path from that node to a leaf  The path means the number of nodes we encounter while traversing the tree between two nodes  In order to achieve O log n  time complexity  the tree should be balanced  meaning that the difference of the height between the children of any node should be less than or equal to 1  Therefore  trees do not always guarantee a time complexity O log n   unless they are balanced  Actually in some cases  the time complexity of searching in a tree can be O n  in the worst case scenario   You can take a look at the balance trees such as AVL tree  This one works on balancing the tree while inserting data in order to keep a time complexity of  log n  while searching in the tree

User · Answer

Simply put  At each step of your algorithm you can cut the work in half   Asymptotically equivalent to third  fourth

User · Answer

O log N  basically means time goes up linearly while the n goes up exponentially  So if it takes 1 second to compute 10 elements  it will take 2 seconds to compute 100 elements  3 seconds to compute 1000 elements  and so on    It is O log n  when we do divide and conquer type of algorithms e g binary search  Another example is quick sort where each time we divide the array into two parts and each time it takes O N  time to find a pivot element  Hence it  N O log N

User · Answer

Algorithms in the Divide and Conquer paradigm are of complexity O logn   One example here  calculate your own power function   int power int x  unsigned int y        int temp      if  y    0          return 1      temp   power x  y 2       if  y 2    0          return temp temp      else         return x temp temp      from http   www geeksforgeeks org write-a-c-program-to-calculate-powxn

User · Answer

It simply means that the time needed for this task grows with log n   example   2s for n   10  4s for n   100        Read the Wikipedia articles on Binary Search Algorithm and Big O Notation for more precisions

User · Answer

But what exactly is O log n    What it means precisely is  as n tends towards infinity  the time tends towards a log n  where a is a constant scaling factor    Or actually  it doesn t quite mean that  more likely it means something like  time divided by a log n  tends towards 1     Tends towards  has the usual mathematical meaning from  analysis   for example  that  if you pick any arbitrarily small non-zero constant k  then I can find a corresponding value X such that   time  a log n    - 1  is less than k for all values of n greater than X      In lay terms  it means that the equation for time may have some other components  e g  it may have some constant startup time   but these other components pale towards insignificance for large values of n  and the a log n  is the dominating term for large n   Note that if the equation were  for example      time n    a   blog n    cn   dnn      then this would be O n squared  because  no matter what the values of the constants a  b  c  and non-zero d  the d n n term would always dominate over the others for any sufficiently large value of n   That s what bit O notation means  it means  what is the order of dominant term for any sufficiently large n

User · Answer

But what exactly is O log n   For example  what does it mean to say that the height of a  complete binary tree is O log n     I would rephrase this as  height of a complete binary tree is log n    Figuring the height of a complete binary tree would be O log n   if you were traversing down step by step        I cannot understand how to identify a function with a logarithmic   time    Logarithm is essentially the inverse of exponentiation   So  if each  step  of your function is eliminating a factor of elements from the original item set  that is a logarithmic time algorithm    For the tree example  you can easily see that stepping down a level of nodes cuts down an exponential number of elements as you continue traversing  The popular example of looking through a name-sorted phone book is essentially equivalent to traversing down a binary search tree  middle page is the root element  and you can deduce at each step whether to go left or right

User · Answer

I can add something interesting  that I read in book by Kormen and etc  a long time ago  Now  imagine a problem  where we have to find a solution in a problem space  This problem space should be finite    Now  if you can prove  that at every iteration of your algorithm you cut off a fraction of this space  that is no less than some limit  this means that your algorithm is running in O logN  time   I should point out  that we are talking here about a relative fraction limit  not the absolute one  The binary search is a classical example  At each step we throw away 1 2 of the problem space  But binary search is not the only such example  Suppose  you proved somehow  that at each step you throw away at least 1 128 of problem space  That means  your program is still running at O logN  time  although significantly slower than the binary search  This is a very good hint in analyzing of recursive algorithms  It often can be proved that at each step the recursion will not use several variants  and this leads to the cutoff of some fraction in problem space

User · Answer

Every time we write an algorithm or code we try to analyze its asymptotic complexity  It is different from its time complexity   Asymptotic complexity is the behavior of execution time of an algorithm while the time complexity is the actual execution time  But some people use these terms interchangeably   Because time complexity depends on various parameters viz           1  Physical System          2  Programming Language          3  coding Style          4  And much more          The actual execution time is not a good measure for analysis       Instead we take input size as the parameter because whatever the code is  the input is same  So the execution time is a function of input size   Following is an example of Linear Time Algorithm    Linear Search  Given n input elements  to search an element in the array you need at most  n  comparisons  In other words  no matter what programming language you use  what coding style you prefer  on what system you execute it  In the worst case scenario it requires only n comparisons The execution time is linearly proportional to the input size   And its not just search  whatever may be the work  increment  compare or any operation  its a function of input size   So when you say any algorithm is O log n  it means the execution time is log times the input size n   As the input size increases the work done here the execution time  increases  Hence proportionality         n      Work       2     1 units of work       4     2 units of work       8     3 units of work   See as the input size increased the work done is increased and it is independent of any machine  And if you try to find out the value of units of work  It s actually dependent onto those above specified parameters It will change according to the systems and all

User · Answer

O log n  refers to a function  or algorithm  or step in an algorithm  working in an amount of time proportional to the logarithm  usually base 2 in most cases  but not always  and in any event this is insignificant by big-O notation   of the size of the input   The logarithmic function is the inverse of the exponential function  Put another way  if your input grows exponentially  rather than linearly  as you would normally consider it   your function grows linearly   O log n  running times are very common in any sort of divide-and-conquer application  because you are  ideally  cutting the work in half every time  If in each of the division or conquer steps  you are doing constant time work  or work that is not constant-time  but with time growing more slowly than O log n    then your entire function is O log n   It s fairly common to have each step require linear time on the input instead  this will amount to a total time complexity of O n log n    The running time complexity of binary search is an example of O log n   This is because in binary search  you are always ignoring half of your input in each later step by dividing the array in half and only focusing on one half with each step  Each step is constant-time  because in binary search you only need to compare one element with your key in order to figure out what to do next irregardless of how big the array you are considering is at any point  So you do approximately log n  log 2  steps   The running time complexity of merge sort is an example of O n log n   This is because you are dividing the array in half with each step  resulting in a total of approximately log n  log 2  steps  However  in each step you need to perform merge operations on all elements  whether it s one merge operation on two sublists of n 2 elements  or two merge operations on four sublists of n 4 elements  is irrelevant because it adds to having to do this for n elements in each step   Thus  the total complexity is O n log n     Remember that big-O notation  by definition  constants don t matter  Also by the change of base rule for logarithms  the only difference between logarithms of different bases is a constant factor

User · Answer

If you had a function that takes   1 millisecond to complete if you have 2 elements  2 milliseconds to complete if you have 4 elements  3 milliseconds to complete if you have 8 elements  4 milliseconds to complete if you have 16 elements      n milliseconds to complete if you have 2 n elements    Then it takes log2 n  time  The Big O notation  loosely speaking  means that the relationship only needs to be true for large n  and that constant factors and smaller terms can be ignored

User · Answer

You can think of O log N  intuitively by saying the time is proportional to the number of digits in N   If an operation performs constant time work on each digit or bit of an input  the whole operation will take time proportional to the number of digits or bits in the input  not the magnitude of the input  thus  O log N  rather than O N    If an operation makes a series of constant time decisions each of which halves  reduces by a factor of 3  4  5    the size of the input to be considered  the whole will take time proportional to log base 2  base 3  base 4  base 5     of the size N of the input  rather than being O N    And so on

User · Answer

What s logb n      It is the number of times you can cut a log of length n repeatedly into b equal parts before reaching a section of size 1

User · Answer

First I recommend you to read following book   Algorithms  4th Edition    Here is some functions and their expected complexities  Numbers are indicating statement execution frequencies     Following Big-O Complexity Chart also taken from bigocheatsheet   Lastly very simple showcase there is shows how it is calculated   Anatomy of a program   s statement execution frequencies   Analyzing the running time of a program  example

User · Answer

The best way I ve always had to mentally visualize an algorithm that runs in O log n  is as follows   If you increase the problem size by a multiplicative amount  i e  multiply its size by 10   the work is only increased by an additive amount   Applying this to your binary tree question so you have a good application  if you double the number of nodes in a binary tree  the height only increases by 1  an additive amount    If you double it again  it still only increased by 1    Obviously I m assuming it stays balanced and such    That way  instead of doubling your work when the problem size is multiplied  you re only doing very slightly more work  That s why O log n  algorithms are awesome

User · Answer

Overview  Others have given good diagram examples  such as the tree diagrams  I did not see any simple code examples  So in addition to my explanation  I ll provide some algorithms with simple print statements to illustrate the complexity of different algorithm categories    First  you ll want to have a general idea of Logarithm  which you can get from https   en wikipedia org wiki Logarithm   Natural science use e and the natural log  Engineering disciples will use log 10  log base 10  and computer scientists will use log 2  log base 2  a lot  since computers are binary based  Sometimes you ll see abbreviations of natural log as ln    engineers normally leave the  10 off and just use log   and log 2 is abbreviated as lg    All of the types of logarithms grow in a similar fashion  that is why they share the same category of log n    When you look at the code examples below  I recommend looking at O 1   then O n   then O n 2   After you are good with those  then look at the others  I ve included clean examples as well as variations to demonstrate how subtle changes can still result in the same categorization   You can think of O 1   O n   O logn   etc as classes or categories of growth  Some categories will take more time to do than others  These categories help give us a way of ordering the algorithm performance  Some grown faster as the input n grows  The following table demonstrates said growth numerically  In the table below think of log n  as the ceiling of log 2      Simple Code Examples Of Various Big O Categories   O 1  - Constant Time Examples    Algorithm 1    Algorithm 1 prints hello once and it doesn t depend on n  so it will always run in constant time  so it is O 1    print  hello      Algorithm 2    Algorithm 2 prints hello 3 times  however it does not depend on an input size  Even as n grows  this algorithm will always only print hello 3 times  That being said 3  is a constant  so this algorithm is also O 1    print  hello   print  hello   print  hello     O log n   - Logarithmic Examples    Algorithm 3 - This acts like  log 2    Algorithm 3 demonstrates an algorithm that runs in log 2 n   Notice the post operation of the for loop multiples the current value of i by 2  so i goes from 1 to 2 to 4 to 8 to 16 to 32       for int i   1  i  lt   n  i   i   2    print  hello      Algorithm 4 - This acts like  log 3    Algorithm 4 demonstrates log 3  Notice i goes from 1 to 3 to 9 to 27     for int i   1  i  lt   n  i   i   3    print  hello      Algorithm 5 - This acts like  log 1 02    Algorithm 5 is important  as it helps show that as long as the number is greater than 1 and the result is repeatedly multiplied against itself  that you are looking at a logarithmic algorithm   for double i   1  i  lt  n  i   i   1 02    print  hello     O n  - Linear Time Examples    Algorithm 6   This algorithm is simple  which prints hello n times   for int i   0  i  lt  n  i      print  hello      Algorithm 7   This algorithm shows a variation  where it will print hello n 2 times  n 2   1 2   n  We ignore the 1 2 constant and see that this algorithm is O n    for int i   0  i  lt  n  i   i   2    print  hello     O n log n   - nlog n  Examples    Algorithm 8   Think of this as a combination of O log n   and O n   The nesting of the for loops help us obtain the O n log n    for int i   0  i  lt  n  i      for int j   1  j  lt  n  j   j   2      print  hello      Algorithm 9   Algorithm 9 is like algorithm 8  but each of the loops has allowed variations  which still result in the final result being O n log n    for int i   0  i  lt  n  i   i   2    for int j   1  j  lt  n  j   j   3      print  hello     O n 2  - n squared Examples    Algorithm 10   O n 2  is obtained easily by nesting standard for loops   for int i   0  i  lt  n  i      for int j   0  j  lt  n  j        print  hello      Algorithm 11   Like algorithm 10  but with some variations   for int i   0  i  lt  n  i      for int j   0  j  lt  n  j   j   2      print  hello     O n 3  - n cubed Examples    Algorithm 12   This is like algorithm 10  but with 3 loops instead of 2   for int i   0  i  lt  n  i      for int j   0  j  lt  n  j        for int k   0  k  lt  n  k          print  hello      Algorithm 13   Like algorithm 12  but with some variations that still yield O n 3    for int i   0  i  lt  n  i      for int j   0  j  lt  n   5  j   j   2      for int k   0  k  lt  n  k   k   3        print  hello     Summary  The above give several straight forward examples  and variations to help demonstrate what subtle changes can be introduced that really don t change the analysis  Hopefully it gives you enough insight

User · Answer

log x to base b   y is the inverse of b y   x  If you have an M-ary tree of depth d and size n  then    traversing the whole tree   O M d    O n  Walking a single path in the tree   O d    O log n to base M

User · Answer

If you plot a logarithmic function on a graphical calculator or something similar  you ll see that it rises really slowly -- even more slowly than a linear function    This is why algorithms with a logarithmic time complexity are highly sought after  even for really big n  let s say n   10 8  for example   they perform more than acceptably

User · Answer

Divide and conquer algorithms usually have a logn component to the running time  This comes from the repeated halving of the input   In the case of binary search  every iteration you throw away half of the input  It should be noted that in Big-O notation  log is log base 2   Edit  As noted  the log base doesn t matter  but when deriving the Big-O performance of an algorithm  the log factor will come from halving  hence why I think of it as base 2

User · Answer

In information technology it means that     f n  O g n   If there is suitable constant C and N0 independent on N     such that   for all N gt N0   C g n   gt  f n   gt  0  is true    Ant it seems that this notation was mostly have taken from mathematics   In this article there is a quote  D E  Knuth   BIG OMICRON AND BIG OMEGA AND BIG THETA   1976      On the basis of the issues discussed here  I propose that members of   SIGACT  and editors of computer science and mathematics journals    adopt notations as defined above  unless a better alternative can be   found reasonably soon    Today is 2016  but we use it still today     In mathematical analysis it means that     lim  f n  g n   Constant  where n goes to  infinity   But even in mathematical analysis sometimes this symbol was used in meaning  C g n    f n    0    As I know from university the symbol was intoduced by German mathematician Landau  1877-1938

User · Answer

O log n  is a bit misleading  more precisely it s O log2 n   i e   logarithm with base 2    The height of a balanced binary tree is O log2 n   since every node has two  note the  two  as in log2 n  child nodes  So  a tree with n nodes has a height of log2 n   Another example is binary search  which has a running time of O log2 n  because at every step you divide the search space by 2

User · Answer

I can give an example for a for loop and maybe once grasped the concept maybe it will be simpler to understand in different contexts   That means that in the loop the step grows exponentially  E g    for  i 1  i lt  n  i i 2        The complexity in O-notation of this program is O log n    Let s try to loop through it by hand  n being somewhere between 512 and 1023  excluding 1024    step  1   2   3   4   5    6    7    8     9     10    i  1   2   4   8   16   32   64   128   256   512   Although n is somewhere between 512 and 1023  only 10 iterations take place  This is because the step in the loop grows exponentially and thus takes only 10 iterations to reach the termination      The logarithm of x  to the base of a  is the reverse function of a x       It is like saying that logarithm is the inverse of exponential    Now try to see it that way  if exponential grows very fast then logarithm grows  inversely  very slow   The difference between O n  and O log n   is huge  similar to the difference between O n  and O a n   a being a constant

User · Answer

Logarithmic running time  O log n   essentially means that the running time grows in proportion to the logarithm of the input size - as an example  if 10 items takes at most some amount of time x  and 100 items takes at most  say  2x  and 10 000 items takes at most 4x  then it s looking like an O log n  time complexity

User · Answer

O logn  is one of the polynomial time complexity to measure the runtime performance of any code   I hope you have already heard of Binary search algorithm   Let s assume you have to find an element in the array of size N   Basically  the code execution is like N N 2 N 4 N 8    etc  If you sum all the work done at each level you will end up with n 1 1 2 1 4      and that is equal to O logn

User · Answer

Actually  if you have a list of n elements  and create a binary tree from that list  like in the divide and conquer algorithm   you will keep dividing by 2 until you reach lists of size 1  the leaves    At the first step  you divide by 2  You then have 2 lists  2 1   you divide each by 2  so you have 4 lists  2 2   you divide again  you have 8 lists  2 3 and so on until your list size is 1  That gives you the equation    n  2 steps  1  lt   gt  n 2 steps  lt   gt  lg n  steps    you take the lg of each side  lg being the log base 2

User · Answer

The complete binary example is O ln n  because the search looks like this   1 2 3 4 5 6 7 8 9 10 11 12   Searching for 4 yields 3 hits  6  3 then 4  And log2 12   3  which is a good apporximate to how many hits where needed

User · Answer

The logarithm  Ok let s try and fully understand what a logarithm actually is    Imagine we have a rope and we have tied it to a horse  If the rope is directly tied to the horse  the force the horse would need to pull away  say  from a man  is directly 1     Now imagine the rope is looped round a pole  The horse to get away will now have to pull many times harder  The amount of times will depend on the roughness of the rope and the size of the pole  but let s assume it will multiply one s strength by 10  when the rope makes a complete turn     Now if the rope is looped once  the horse will need to pull 10 times harder  If the human decides to make it really difficult for the horse  he may loop the rope again round a pole  increasing it s strength by an additional 10 times  A third loop will again increase the strength by a further 10 times      We can see that for each loop  the value increases by 10  The number of turns required to get any number is called the logarithm of the number i e  we need 3 posts to multiple your strength by 1000 times  6 posts to multiply your strength by 1 000 000    3 is the logarithm of 1 000  and 6 is the logarithm of 1 000 000  base 10    So what does O log n  actually mean    In our example above  our  growth rate  is O log n   For every additional loop  the force our rope can handle is 10 times more    Turns   Max Force   0       1   1       10   2       100   3       1000   4       10000   n       10 n   Now the example above did use base 10  but fortunately the base of the log is insignificant when we talk about big o notation    Now let s imagine you are trying to guess a number between 1-100   Your Friend  Guess my number between 1-100   Your Guess  50 Your Friend  Lower  Your Guess  25 Your Friend  Lower  Your Guess  13 Your Friend  Higher  Your Guess  19 Your Friend  Higher  Your Friend  22 Your Guess  Lower  Your Guess  20 Your Friend  Higher  Your Guess  21 Your Friend  YOU GOT IT      Now it took you 7 guesses to get this right  But what is the relationship here  What is the most amount of items that you can guess from each additional guess   Guesses   Items   1         2   2         4   3         8   4         16   5         32   6         64   7         128   10        1024   Using the graph  we can see that if we use a binary search to guess a number between 1-100 it will take us at most 7 attempts  If we had 128 numbers  we could also guess the number in 7 attemps but 129 numbers will takes us at most 8 attempts  in relations to logarithms  here we would need 7 guesses for a 128 value range  10 guesses for a 1024 value range  7 is the logarithm of 128  10 is the logarithm of 1024  base 2     Notice that I have bolded  at most   Big-O notation always refers to the worse case  If you re lucky  you could guess the number in one attempt and so the best case is O 1   but that s another story       We can see that for every guess our data set is shrinking  A good rule of thumb to identify if an algorithm has a logarithmtic time is   to see if the data set shrinks by a certain order after each iteration    What about O n log n    You will eventually come across a linearithmic time O n log n   algorithm  The rule of thumb above applies again  but this time the logarithmic function has to run n times e g  reducing the size of a list n times  which occurs in algorithms like a mergesort    You can easily identify if the algorithmic time is n log n  Look for an outer loop which iterates through a list  O n    Then look to see if there is an inner loop  If the inner loop is cutting reducing the data set on each iteration  that loop is  O log n    and so the overall algorithm is   O n log n    Disclaimer  The rope-logarithm example was grabbed from the excellent Mathematician s Delight book by W Sawyer

User · Answer

Many good answers have already been posted to this question  but I believe we really are missing an important one - namely  the illustrated answer      What does it mean to say that the height of a complete binary tree is O log n     The following drawing depicts a binary tree  Notice how each level contains double the number of nodes compared to the level above  hence binary      Binary search is an example with complexity O log n   Let s say that the nodes in the bottom level of the tree in figure 1 represents items in some sorted collection  Binary search is a divide-and-conquer algorithm  and the drawing shows how we will need  at most  4 comparisons to find the record we are searching for in this 16 item dataset   Assume we had instead a dataset with 32 elements  Continue the drawing above to find that we will now need 5 comparisons to find what we are searching for  as the tree has only grown one level deeper when we multiplied the amount of data  As a result  the complexity of the algorithm can be described as a logarithmic order   Plotting log n  on a plain piece of paper  will result in a graph where the rise of the curve decelerates as n increases

User · Answer

In simple words   The next iteration of the loop takes double the time the current one took --  n 2  The next iteration of the loop takes same the time the current one is going to take --  n  The next iteration of the loop takes half the time the current one is going to take --  log2 n   The next iteration of the loop takes 1 3rd the time the current one is going to take --  log3 n   The next iteration of the loop takes 1 4th the time the current one is going to take --  log4 n   When it comes to Asymptotic analysis  we just call log n  which can be basically any base as shown above  But since we computer scientists use binary trees more than other types of trees  we end up with log2 n  most of the times which we just term log n

[algorithm] What does O(log n) mean exactly?

Examples related to algorithm

Examples related to time-complexity

Examples related to big-o