Big O Note and Not Borrowing from a Class Lecture

Question

I have this problem when in class my professor said that the expression below is O(log(n)) , where I thought it was O(n) . Can someone clarify how this is O(log(n)) ?

Printing a number of magnitude n in binary. Assume that printing each bit requires constant time.

Answer 1

You should work out some examples. Write some numbers in binary format. For example, how many bits are in 63, 255 and 511? Note that the number of bits does not grow almost as fast as the number itself.

Answer 2

This is O (log (n)) because you have to divide by 2 every time you are going to print 0 or 1 . For example, to print 256 in binary format, you would have to divide by 2, starting at 256, and print the result % 2 each time.

 256 % 2 -> 0 64% 2 -> 0 32 % 2 -> 0 16 % 2 -> 0 8 % 2 -> 0 4 % 2 -> 0 2 % 2 -> 0 1 % 2 -> 1 

So, for some 256 you will need to repeat 8 times, equal to log 256 .

Answer 3

O (log (n)) is all about cutting data by half. When each step of the algorithm eliminates a fraction of the remaining input - for example, you always reduce the space in half or by the third or even to 99/100 of the previous step - this algorithm works in O (log (n)) time.

hope this helps