Data Science PT 7: Computational Complexity/Algorithm Design

Computational Complexity is defined as the "formal classification of functions based on rate of asymptotic growth". There are many different types of growth. Θ(g(n)) is a tight asymptotic bound, O(g(n)) is the upper bound for f(n), Ω(g(n)) is the lower bound for f(n), and f(n)=o(g(n)) is where the ratio f(n)/g(n) vanishes.

Let's now go over a formal example proof to demonstrate computational complexity.  We will show that n^2 - 3n = Θ(n^2). 

Θ(g(n)) = {f(n): ∃c1, c2, N0>0 s.t. 0 < c1g(n) ≤ f(n) ≤ c2g(n), which means that there exists a c1 and c2 where the runtime is greater than c1g(n) but less than c2g(n). The other definitions are as follows: 

Θ(g(n)) = {f(n): ∃c1, c2, N0>0 s.t. 0 < c1g(n) ≤ f(n) ≤ c2g(n), ∀n>N0}

O(g(n)) = {f(n): ∃c, N0>0 s.t. 0 < f(n) ≤ cg(n), ∀n>N0}[Asymptotic Upper Bound]

Here are some examples of certain time complexities and the algorithms they can solve: 

Low Complexity:

Θ(1) – run few simple lines of code 

Θ(log(n)) – searching for element in balanced tree data structure (will learn) 

Θ(n^0.5) – determine whether a number is prime

Medium Complexity: 

Θ(n) – find min/max among n numbers 

Θ(n×log(n)) – Sort n numbers – Fast Fourier transform (FFT) 

Θ(n^2) – Matrix vector product (n×n matrix) – Direct computation of discrete Fourier transform (DFT) 

Θ(n^3) – matrix inversion

High Complexity:

Θ(2^n * f(n)) – optimally decode n bits 

Θ(n! * f(n)) – process all permutations of n objects 

Suffix sorting is used in data compression algorithms. Suffix trees has a linear (Θ(n)) worst case. Square root time complexity is a lot better way than just (n^1) power time.

Ω(g(n)) = {f(n): ∃c, N0>0 s.t. 0 < cg(n) ≤ f(n), ∀n>N0} [Asymptotic Lower Bound] 

f(n)=o(g(n)) means limn->∞f(n)/g(n)=0 

Now let's talk about Algorithm Design. 

Many computational problems can be classified in a Divide-And-Conquer Approach, where we 1.Divide problem into sub-problems 2. Conquer each sub-problem recursively 3. Combine solutions. We will solve directly if a problem is small enough, else apply recursion to sub-problems if the problem is big enough. Let C(N) be combining, and let D(N) be dividing. Then, the recursive formula is as follows: 

Let's go over a question which tries to compute n distinct numbers. All we gotta do is run merge sort in n log n time and compute this algorithm in O(n) time: 

for i = 1 to n-1

    if x(i) = x(i + 1) 

    then there is a repeat occurance

        break/return

else continue looping

The algorithm in total runs in O(n + nlogn) or O(nlogn) time.

In the future, we  might even get quantum speedups in the futures. 

The last part in the article is to show that N! = O(N^N).

In the blue part of the problem we can choose c1 = ad−ε, c2 = ad + ε, proving that

.

Because the limit is 0 for anything smaller than d in the blue part we can safely say and there exists some large N0 that satisfies the condition. The rate of growth of a polynomial is a monomial whose exponent is the polynomial’s greatest exponent.