http://www.codenlearn.com/2011/07/understanding-algorithm-complexity.html
https://www.quora.com/How-would-you-explain-O-log-n-in-algorithms-to-1st-year-undergrad-student

Hardware execution time

Let’s say an assignment

is one step.

This requires the same amount of time no matter how big the length of array is. We can say that time, T, to insert an item into an unsorted array is a constant K:

T = K

In detail, the actual time (in ms or whatever unit of measure) is required by the insertion is:

• related to the speed of the microprocessor
• how efficiently the compiler has generated the program code
• ..other factors

Linear Search

The number of comparisons that must be made to find a specified item is, ON AVERAGE, half of the total number of items. Hence, if N is the total number of items, the search time T is

N = number of items
T = time
K = execution time of hardware

T = K * (N / 2)

For a handier formula, we can lump the 1/2 into the K, because we are dealing with constant numbers. Hence we can say a constant K is
some constant K which represents execution time of the hardware divided by 2.

Hence, T = K * N

Time = hardware execution time * Number of items

The reason why we do this is because, we’re not interested in the actual execution time. We’re just interested in how fast the algorithm is running IN ACCORDANCE TO THE NUMBER OF ELEMENTS N.

Thus, whatever execution time is for the particular processor and compiler at the time does not matter to us. Whether its a 333mhz processor or a 3ghz processor, it doesn’t matter.

We just lump that constant numeric together and pull out the number of elements N SO THAT we can convey how running times are affected by the number of items.

This says that average linear search times are proportional so the size of the array.

For example,

In an unordered array, Search takes O(N) time because you need to go through N/2 elements on average. Multiple that that by processing time constant K time T = (N/2) * K = K * N = O(N) where we don’t care about literal processing time of K.

In an unordered array, Deletion takes O(N) time because once you use Search to find the element to delete, you still need to shift elements down to fill the empty spot. On average its N/2 elements that you need to shift down. Multiple that by processing time constant K time T = (N/2) * K = K * N = O(N) where we don’t care about processing time of K.

Binary Searching

T is time
K is hardware execution time
N is number of items

T = K * log (base 2) N

But because whether we’re dealing with binary three, or tinery tree, or whatever, base 2, base 3…etc is simply a constant numeric. i.e lay out a base 2 framework and a base 10 framework, their difference is 3.322. That’s a numeric that we can include into the constant K.

Hence, T = K * log N.

Eliminating the Constant K for Big O

When comparing algorithms you don’t really care about the particular microprocessor chip or compiler, all you want to compare is how T changes for different values of N. Therefore, the constant isn’t needed.

Big O notation uses the uppercase letter O, which you can think of as meaning “order of”. In Big O notation, we would say that a linear search takes O(N) time, binary search takes O(log N) time. Insertion into an unordered array takes O(1), or constant time.

The idea in Big O notation isn’t to give an actual figure for running time, but to convey how running times are affected by the number of items.

Log(n)

In the case of binary search, you are trying to find the maximum number of iterations, and therefore the maximum number of times the search space can be split in half.

This is accomplished by dividing the size of the search space n, by 2 repeatedly until you get to 1 number.

Let’s give the number of times you need to divide n by 2 the label x. Since dividing by 2 x times is equivalent to dividing by 2^x, you end up having to solve for this equation:

n total number of items
x number of times you need to divide by 2 to get the result 1

n / 2^x = 1

x is the number of times you can split a space of size n in half before it is narrowed down to size 1.
The solution to this equation be found by taking the logarithm of both sides:

2^x = n

by log mathematical inductions….

log (2^x) = log (n^1)

x log 2 = 1 * log n

x = log ( n ) / log ( 2 ) = log base 2 (n)

Hence

x = log base 2 (n)

means that given n numbers, x is the number of times we split those n numbers in half, in order to get a result of 1.