How to calculate O(Log(N))?

Question

I want to know exactly how to calculate O(Log(N)) for this exemple : we have a sorted array of 10 elements [1 3 4 8 10 15 18 20 25 30] When we do a normal search we have a complexity of O(10) that means that we have to check every case of the array so O(10) = 10. but if we do a dichotomic search because we have a sorted array we have a complexity of (O(Log(10)) what's is the result of this notation O(Log(10))= ??? ? i have a missunderstand shall we use Log base 10 or 2 or what exactly ? thanks for the help

Solution 1

You have misunderstood the concepts of algorithmic order of growth. Please read a book on algorithms and get your concepts strong. In any case I'll try explaining at a high level,

If you have an array of 10 elements like you said, and you do a "normal search" (It's called Linear Search) you are iterating through each element in the array, which means that if there are 'n' elements 'n' elements have to be checked. So it's O(n) not O(10). If it were O(10) [ btw, O(10) = O(1) ] that would mean that the it would always take 10 iterations or less, no matter how many elements there were in the array, which is not the case. If your array had 100 elements, it would take 100 iterations so we say the order is O(n) where n is the input size (here the size of the array).

The above method is for a non sorted array, for a sorted array we can use a faster method to search, much like how you would look up a word in a dictionary, this technique is called Binary Search. What happens here is, you look up the middle element of the array and see where the number you are searching for lies, either on the first half or the next half. Then, you select the half you want and apply the same method of dividing into half and checking. Since this is being done recursively, it uses logarithmic growth (in case of binary search, it is log to base 2). Please read up on Binary Search and logarithmic order of growth for a better understanding.

Solution 2

I think you are confused about why a binary search is log(n) and why it's base 2. Think of it this way, at every step in your binary search , you are reducing your input size by 2. How many times do you need to do this ? You need to do this log n to the base 2 times in order to reduce your sample size to 1.

For example if you have 4 elements, first step reduces the search to 2, the second step reduces the search to 1 and you stop. Thus you had to do it log (4) to the base 2 = 2 times. In other words if log n base 2 = x, 2 raised to power x is n.

So if you are doing a binary search your base will be 2. More clearly, in your case Log(10) base 2 will be something around 3.3 i.e you will be making at most 4 comparisons.

Solution 3

I'm afraid that's not how asymptotics work. Big-O notation is intended to describe how an algorithm scales for variable size input. In particular, the number of operations needed by an algorithm on a fixed input (as yours above) will always be constant, i.e., O(1). Similarly, big-O notation is invariant to constant multiplication. This means that:

• O(1) = O(10) = O(Log(10))
• The basis of your logarithm doesn't matter, since changing the base introduces only a constant factor

Solution 4

i have a missunderstand shall we use Log base 10 or 2 or what exactly

It does not matter. The complexity does not change. Log base 2 is the same as:

Log_2(N) = Log(N) / Log(2)

Both are elements of O(Log(N)).

View more solutions

Comments

[satyres]

thanks for the comment ,in a normal array in order to search for an item i have to look after every case so O(10)= 10 right ! but what's the result for dichotomic serach O(Log(10)) thanks ?

[satyres]

thanks for the comment , my problem is i have an algorithmic problem that i want to resolve but i have the constraint of execution of 2 seconds in a CPU of 1 GHZ, so i wonder how to calculate exactly the complexity to know if my algorithm is correct or not when i have i want to calculate O(Log(N)) i'm blocked

[Amal Antony]

@satyres: Read on "order of growth", either from a book or online. Only that can help you understand better. Your ideas are very wrong.

[satyres]

can you give me a link please !

[Amal Antony]

@satyres: Start here: en.wikipedia.org/wiki/Big_O_notation. There is a introductory book on Algorithms by Anany Levitin. It has a good introduction to analyzing algorithms.

[G. Bach]

I'd actually advise against wikipedia for this; their technical sites often times are convoluted and overly broad for a beginnner, which to me seems to be the case regarding the site on Landau and O-notation. Maybe this introductory material by MIT is more suitable for beginners.

[Nick Mitchinson]

Try watching this <a href="youtube.com/… playlist</a> which is about asymptotic analysis

[kumarharsh]

although I don't disagree with the other answers, this one comes closest to solving the question. And @satyres as for a course on Algorithms, the MIT lectures would be good. Or try the fantastic Khan Academy, I think they should have topics on this too