Understand Algorithm Evaluation and Basic Algorithms

Photo by David Clode on Unsplash

The main indicator to evaluate algorithms is the speed to process data. The major way to evaluate the speed of the algorithm is Big O notation.

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.(wikipedia: Big O notation)

In other word, Big O(Order) notation is the calculation ability of the functions according to how these run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also referred to as the order of the function.

There are the two key words to understand Big O notation like the below:
Time complexity: time to finish the function execution
Space complexity: memory to use for the function execution

Time complexity is the same as space complexity but the usage is different.

Representations of Big O notation:
O(1) > O(log n) > O(n) >O(n log n)> O(n2) > O(n3) > O(nn)

This image is created by Jesse Tetsuya.

Coding examples:

References of time complexity:

• Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)
• The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)

Algorithm approach

There are two kinds of approaches and three algorithms to process data.

This image is created by Jesse Tetsuya.

Bottom up approach:

small number -> big number

for i in range(5):
    print(i)
-> 0,1,2,3,4

Top down approach:

big number -> small number

def recursion(N):
    if N < 2:
        return N
    print(N)
    return recursion(N-1)
recursion(5)
-> 5, 4, 3, 2, 1

1)Brute force

= for loop

2)Divide and Conquer

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

In short word, divide a problem into a few subproblems or more.
=recursion

3)Dynamic algorithm

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. On the top of that, store the result and re-use it.

In short word, divide a problem into a few subproblems or more and re-use the results of them.
- recursion or for loop
- memoization

CASE STUDY with Fibonacci Sequence:

References of Algorithm:

• 19. Dynamic Programming I: Fibonacci, Shortest Paths

Recursion

Three steps to implement Recursion:

1. Base case — Think of the simplest possible input for this function
2. Find the relation — Think how the larger problem can be solved with the help of the solution of the smaller problem
3. Generalize —Make a generalized function that solves the problem. Put this all together into a Mathematical function or a Tree.

Six Recursive Patterns:

1. Iteration — ex) Linked List in reverse order, Factorial, For loop
2. Breaking Into Subproblems — ex) Towers of Hanoi, Fibonacci
3. Selection — ex) Knapsack, Word break…etc.
4. Ording — ex) Permutationse…etc.
5. Divide and Conquer — ex) Mergesort, Generate all BSTs for a set of items
6. Depth First Search — ex) Search in a tree…etc.

Tree representation of Fibonacci Sequence:

You should understand the below picture following the code of divide and conquer approach by recursion and the code of recursion with memoization.

Sort algorithms

Learning sort algorithms can be a good stepping stone to learn the core principle of the algorithms.

This is the basic sort algorithms and the speed ability of each here.

This image is created by Jesse Tetsuya.

• Bubble sort: a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

• Selection sort: the selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

• Insertion sort: the array elements are compared with each other sequentially and then arranged simultaneously in some particular order.

• Quick sort: a type of Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot

• Merge sort: a type of Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The point is that the numbers are sorted just when the numbers are merged.

Search, Stack, and Queue

• Search: the algorithm to find the number which you want. There are three kinds of basic search algorithms such as linear search, binary search, and binary search with recursion. The input data of the below code is sorted in order.

• Stack: a stack is an abstract data type that serves as a collection of elements, with two main principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.

• Queue: a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).

＊ deque allows us to add and remove from both sides of queue. While List needs O(n) to add and remove by using insert() and pop(), deque has append(), appendleft(), pop(), and popleft() which are O(1).