#complexity analysis

[nick1100]

Understanding log n complexity

Binary search, mergesort, quicksort, AVL Trees, Splay trees, B-trees and red-black trees, etc. are only some algorithms or data structures that $ log \, n $ is related to. But what does it mean, really? Can we think intuitively about it?

I believe one intuitive way of thinking about $ log \, n $ complexity is: How many times can $ n $ be divided in halves until reaching $ 1 $?

This is a good way to think about it, but let’s show why we can think of it that way. I’m aware of that there are many attempts for explaining this in an intuitive way out there, but I remember myself that I was not really satisfied until I got to the more mathematical way of seeing it.

Let's see how many times $ n $ can be divided until we reach $ 1 $.

$$ n / 2 $$ $$ \frac{\frac{n}{2}}{2} = \frac{n}{2} \cdot \frac{1}{2} = \frac{n}{2^2} $$ $$ \frac{n}{2^2} \cdot \frac{1}{2} = \frac{n}{2^3} $$ $$ \frac{n}{2^3} \cdot \frac{1}{2} = \frac{n}{2^4} $$ $$ \frac{n}{2^4} \cdot \frac{1}{2} = \frac{n}{2^5} $$ $$ \frac{n}{2^5} \cdot \frac{1}{2} = \frac{n}{2^6} $$ $$ ... $$ $$ \frac{n}{2^x} = 1 $$

Note: Dividing by $ 2 $ is the same as multiplying with its multiplicative inverse $ \frac{1}{2} $.

So we keep dividing by 2 until we get $ 1 $, where $ x $ is how many times we have divided. See how we're actually left with an equation, namely

$$ \frac{n}{2^x} = 1 \Leftrightarrow 2^x = n. $$

Recall from logarithms in your math class (if you need to refresh, read my post

about it) that this is an exponential equation that can be solved easily using the definitions of logarithms $$ 2^x = n \Rightarrow x = log_2 n $$

So what did we end up with? $ log \, n $, just what we wanted.

Conclusions

First I suggested an intuitive way of thinking about logarithms; how many times $ n $ could be divided in halves until reaching one. This is a really useful property, because it's used in computer science all the time when talking about trees (and other applications). For instance, the height of a complete binary tree is at most $ log_2 \, n $.

Then we saw how we could come up with this in a mathematical way.

Not really a long post, but it's pretty concrete. Ask any questions you might have in the comments field. =)

[nick1100]

Selection Sort

Another simple sorting algorithm is the famous Selection Sort. It works a bit similiar to Bubble Sort, but instead of comparing each adjacent pair and let the sorted elements “bubble up” we start at the beginning element and search through the whole list to find the minimum element, and then we swap them, and then advance to the next element. This process continues until we can consider the whole list to be sorted.

Pseudo code

Let $ A $ be a sortable array $ A[0..n-1] $

for i = 0 to n - 2 min = i for j = i + 1 to n - 1 if A[min] > A[j] then min = j swap(A[min], A[i])

An invariant for selection sort that holds true could be that after each iteration in the outer loop the first $ i $ elements are considered sorted.

Example

A bold element is the minimum element found in the specific iteration and that should be swapped. Underlined elements are those that we consider sorted, e.g. in correct order, and don't need to be compared again.

Let's sort the following list $$ A = [16, 4, 9, 3, 15, 5, 7] $$

[16, 4, 9, 3, 15, 5, 7]

[3, 4, 9, 16, 15, 5, 7]

[3, 4, 9, 16, 15, 5, 7]

[3, 4, 5, 16, 15, 9, 7]

[3, 4, 5, 7, 15, 9, 16]

[3, 4, 5, 7, 9, 15, 16]

[3, 4, 5, 7, 9, 15, 16]

[3, 4, 5, 7, 9, 15, 16]

And sorted! Number comparisons in total needed: $ 21 $.

Implementation in Python

a = [16, 4, 9, 3, 15, 5, 7] for i in range(0, len(a) - 1): for j in range(i + 1, len(a)): if a[j] < a[min]: min = j temp = a[min a[min] = a[i] a[i] = temp

Complexity analysis

The complexity analysis for selection sort is pretty much the same as for bubble sort. Note that, for explanations about the math parts see my explanations for Bubble sort. They are the same here.

Just like for bubble sort, we start translating our for loops into sums, and let $ c(n) $ be our function to count how many times the critical operation executes.

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = i + 1}^{n - 1} 1 = \sum_{i = 0}^{n-2} (n - 1 - i) = \frac{n(n-1)}{2}. $$

Hence, $ c(n) \in \Theta(n^2) $.

Next - Insertion sort

[nick1100]

Bubble Sort algorithm

Bubble sort is a simple sorting algorithm where we sequently step through the list and compare each adjacent pair and swap them if neccessary, i.e. if they are in the wrong order. Then we start over and do the same until we have compared all and thus sorted the list. In this post we’ll take a closer look at the algorithm and do some complexity analysis.

Pseudo code

Let $ A $ be a sortable array $ A[0..n-1] $

for i = 0 to n - 2 for j = 0 to n - 2 if A[j] > A[j+1] then swap(A[j], A[j+1])

An invariant for this to hold true could be that, after each iteration in the outer loop at least one element is guaranteed to be at its right place, so we actually don't need to check the whole list again. This means we can make our pseudo code a little more effective and not let it compare unneccessary elements. We do this by modifying the inner loop a little:

for i = 0 to n - 2 for j = 0 to n - 2 - i if A[j] > A[j+1] then swap(A[j], A[j+1])

Example

An unsorted list with 5 elements, i.e. $ n = 5 $: $ A = [3, 5, 2, 1, 6] $

Underlined elements are in the correct order. Bold elements are those being compared.

$i = 0:$ [3, 5, 2, 1, 6] is $ 3 > 5 $? No, move on.

[3, 5, 2, 1, 6] is $ 5 > 2 $? Yes, swap.

[3, 2, 5, 1, 6] is $ 5 > 1 $? Yes, swap.

[3, 2, 1, 5, 6] is $ 5 > 6 $? No, move on.

$ i = 1: $ [3, 2, 1, 5, 6] is $ 3 > 2 $? Yes, swap.

[2, 3, 1, 5, 6] is $ 3 > 1 $? Yes, swap.

[2, 1, 3, 5, 6] is $ 3 > 5 $? No, move on.

$ i = 2: $ [2, 1, 3, 5, 6] is $ 2 > 1 $? Yes, swap.

[1, 2, 3, 5, 6] is $ 2 > 3 $? No, move on.

$ i = 3: $ [1, 2, 3, 5, 6] is $ 1 > 2$? No, move on.

At this step, the whole array is assumed to be sorted and we're done.

Implementation in Python

a = [3, 5, 2, 1, 6] for i in range(len(a)-1): for j in range(len(a) - 1 - i): // If two adjacent elements are in wrong order, swap them if a[j] > a[j+1]: temp = a[j] a[j] = a[j+1] a[j+1] = temp print(a);

Complexity analysis

This sorting algorithm is pretty slow, but let's see how slow.

As usual we start by writing the sums (they are easily translated from the for loops). Let $ c(n) $ be the function that yields how many times the most critical operation executes in the algorithm (in bubble sort it's obvious, the compare operation). We get

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = 0}^{n - 2 - i} 1 $$

Since $$ \sum_{j = 0}^{n - 2 - i} 1 = (n - 2 - i) - 0 + 1 = n - 1 - i $$

we rewrite the sum to

$$ c(n) = \sum_{i = 0}^{n-2}(n - 1 - i). $$

If we would expand this sum it would look like this $$ (n - 1 - 0) + (n - 1 - 1) + (n - 1 - 2) + .. + 0 $$ i.e. $$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) $$

and this sequence has a known formula:

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) = \frac{n(n-1)}{2}. $$

To summarize, we now have that

$$ c(n) = \sum_{i = 0}^{n-2} \sum_{j = 0}^{n - 2 - i} 1 = \frac{n(n-1)}{2} $$

which means that $ c(n) \in \Theta(n^2) $.

Also, recall that in the example above we saw that the critical operation executed $ 10 $ times for $ n = 5 $ elements. That's reasonable because

$$ \frac{n(n-1)}{2} = \frac{5 \cdot (5 - 1)}{2} = 10. $$

Extra: Proof

Let's prove that

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (n - 1) = \frac{n(n-1)}{2} $$

with mathematical induction.

In all steps, left-hand side (LHS) and right-hand side (RHS) should be equal.

Base case $ n = 2$:

$ LHS = (n - 1) = 2 - 1 = 1 $

$ RHS = \frac{n^2-n}{2} = \frac{2^2-2}{2} = 1 $

$ LHS = RHS $.

Induction step: Assume the statement is true for $ n = k $, e.g.

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) = \frac{k(k-1)}{2} $$

Then it should hold true for $ n = k + 1 $, e.g.

$$ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) + k = \frac{(k+1)((k+1)-1)}{2} = \frac{k(k+1)}{2} $$

Since we assumed that $ 0 + 1 + 2 + 3 + 4 + 5 + .. + (k - 1) = \frac{k(k-1)}{2} $

then it must also hold true that

$$ \frac{k(k-1)}{2} + k = \frac{k(k+1)}{2} $$

Simplify $ LHS $

$$ LHS = \frac{k(k-1)}{2} + k = \frac{k^2-k}{2} + \frac{2k}{2} = \frac{k(k+1)}{2} $$

$ LHS = RHS $.

Next - Selection Sort