What is the Big O Analysis?
O in the Big O is Omega. In programming, time complexity is major issue to optimize the program.
To compare the efficiency of algorithm, we usually use Big O analysis.

Big O notation usually means worst case except quick sort.
in the case of quick sort, big o notation means average case.
There are two point we should know.

First. Ignoring a constant term.

We assume that the input data is large enough and the efficiency of algorithm also affect by size of input data.
So big O notation ignore a constant term.
ex)

O(2n) -> O(n)

Second. Ignoring minor terms.

If input data is large, Bigest terms only impact on time complexity of algorithm.
So big O notation ignore minor terms.
ex)

O(n^2 + 2n + 1) -> O(n^2)

With mathematical prerequistes, we can compare the time complexity.

O(1) : constant

Algorithm only take one step to solve the problem.
it takes same time without any impact from input data.

O(logN) : logarithmic

Algorithm divide the problem as small quantity with same size and then solve it.
it’s proportional to time but the data that we can solve is 2^N.
Binary search is a good example.

O(N) : linear

Algorithm solve the problem linearly.
it’s directly proprotional.
For, linear search are a good example.

O(NlogN) : super linear

Algorithm divide the problem as small quantity and then merge the result after solve each of them.
it’s proportional but it would take much more than linear.
Quick sort and Merge sort are a good example.

O(N^2) : quadratic

Algorithm solve the problem using double for statement.
if input is large enough, time is increasing exponentailly.
This is not a good way to solve the problem.
double for statement, insertion sort, bubble sort are a good example.

So let’s practice to calculate the big O notation.

def func(a+b) :
  return a+b # O(1)

print(func(10+20))

Nonetheless the size of input data, this func works only one time.
It is definitely O(1).

def func(value) :
  print(value) # O(1)
  for i in range(value) :
    print(i, end=', ') # O(N)

func(10)

print value is happening only one time when the func is called. -> O(1).
For state has range as value. so time complexity increase proportional -> O(N).
Big O notation ignore the minor factor.

O(N) + O(1) -> O(N)

Let’s think about binarySearch. To find a target number in the array, binarySearch divide
the problem to small quantity

def binarySearch (arr, left, right, target):
    if right >= left:
        if right >= left:
            mid = left + (right - left)/2
            if arr[mid] == target:
                return mid
            elif arr[mid] > target:
                return binarySearch(arr, left, mid-1, target)
            else:
                return binarySearch(arr, mid+1, right, target)
    else:  
        return -1

arr = [ 10, 20, 30, 40, 50, 60, 70, 90 ]
target = 10
result = binarySearch(arr, 0, len(arr)-1, target)

if result != -1:
    print "Element is present at index %d" % result
else:
    print "Element is not present in array"

you can see the result using the IDEONE

So that’s why binarySearch has O(logN).
the point is divide the problem as smaller one.

like this we can compare the time complexity using Big O analysis.
Practice to calculate Big O to simple code.

furthur more, space complexity is the measure that how algorithm use memory efficiently.
Developer should develop algorithm considering both complexity.

Thank you.