A Little Piece of Me

Hi buddy? many students or even your self talking about analysis algorithm often seen as a scary thing and I agree 100% cos I’m also not really sure about it since I believe analysis algorithm is a large thing and needs a high math knowledge to understand it, and the bad new is I hate talking about mathematics :-). However, through this article I’ll share you about the basics to analysis algorithm based on what I know about it with the hope at least it can help beginners who are trying to analysis algorithm. Finally, this is not as a perfection, there are lots of rooms for improvement or better articles about this stuff. And I state this is just a sharing! 🙂
Well, The first thing we should know is what the algorithm is? If you are a computer science student or such of that, you must be know it. A simple definition, algorithm is the steps to solve a problem that transform the input to be output.

However in computer science, an algorithm isn’t only seen whether that algorithm is correct or can solve the problem, but it must be effective. An algorithm can be said effective if it requires a small space and time to execute its procedures. But, the problem is how can we determine or at least estimate the effectiveness of an algorithm? To answer that question we need to know the asymptotic notations which often used to describe the complexity of an algorithm. Besides that, there is something called Master Theorem that often used to describe the recurrence (running time of recursive algorithm), and much more methods for analyzing the algorithm. (Oh, that’s really bored, I just can hope the scientists stop doing research to find something new ) 😦

Big Oh (O)

Big oh is a mathematics notation that often used to describe the asymptotic function. In computer science Big Oh also can be used to describe how the large input size affects the performance of an algorithm. (I’m sorry, if that’s little confused). In analysis algorithm, Big Oh is often used to describe the worst-case of an algorithm by taking the highest order of a polynomial function and ignoring all the constants value since they aren’t too influential for sufficiently large input. So, if an algorithm has running time like f(n) = 3n + 100, we can simply state that algorithm has the complexity O(n) which means it always execute at most n procedures. Thus, we can guarantee that algorithm would not be bad than the worst-case. So, what’s the idea behind Big Oh? Well, let’s see the definition of Big Oh (I’m sorry if this definition is little confusing because I’m also not really sure what I wrote here and I’m not good in Math).

Definition: Let f(n) and g(n) be non-negative functions. Can be said that f(n) = O(g(n)) (read f(n) is big oh of g(n)) if and only if there are two positive constants C and N such that f(n) ≤ g(n) when n ≥ N.

Example: prove that f(n) = 5n² + 3n + 2 has Big Oh O(n²) !
From the definition of Big Oh, we can say that f(n) = 5n² + 3n + 2 = O(n²), since for all n ≥ 1 : 5n² + 3n + 2 ≤ 5n² + 3n² + 2n² → 5n² + 3n + 2 ≤ 10n² . By assigning the constants C = 10, N = 1, it’s right f(n) ≤ C g(n). Thus, f(n) = 5n² + 3n + 2 → O(g(n)) = O(n²).

Now, is f(n) = 5n + 10 = O(n²)? [Yes/No]

Big Omega (Ω)

Now that you’ve known about Big Oh, what’s about Big Omega? Well, Big Omega is the opposite of Big Oh, if Big Oh was used to describe the upper bound (worst-case) of a asymptotic function, Big Omega is used to describe the lower bound of a asymptotic function. In analysis algorithm, this notation is usually used to describe the complexity of an algorithm in the best-case, which means the algorithm will not be better than its best-case.

Definition: Definition: Let f(n) and g(n) be non-negative functions. Can be said that f(n) = Ω (g(n)) (read f(n) is big omega of g(n)) if and only if there are two positive constants C and N such that C g(n) < f(n) when n ≥ N.

Example: Prove that f(n) = 8n – 15 has Big Omega Ω(n) !
From the definition of Big Omega, we can say that f(n) = 8n – 15 = Ω(n²), since for all n ≥ 1 : 8n – 15n ≤ 8n – 15 → -7n ≤ 8n – 15, since f(n) and g(n) are the non-negative function it can be written to be |-7n| ≤ |8n – 15| → 7n ≤ 8n – 15. By assigning the constants C = 15, N = 1, it’s right C g(n) ≤ f(n) when n ≥ N. Thus, f(n) = 8n – 5 = Ω(n).

With the same way we can say that f(n) = 3n2 + 10n + 6 = Ω(n) = Ω(n2) <> Ω(n3).

Big Theta (Θ)

When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O(n log n) and Ω(n log n), it’s actually has the complexity Θ(n log n), which means the running time of that algorithm always falls in n log n in the best-case and worst-case.

Definition: Let f(n) and g(n) be non-negative functions. Can be said that f(n) = Θ(g(n)) (read f(n) is big theta of g(n)) if and only if there are positive constants C₁, C₂, and N, where f(n) = O(g(n)) and f(n) = Ω(g(n)), such that C₁ g(n) ≤ f(n) ≤ C₂ g(n) when n ≥ N.

Example: Given a function f(n) = 3n² + 10n + 6. Can be said that f(n) = Ω(n²). From the definition of Big Oh and Big Omega, we can conclude that:

Since Big Theta said that function f(n) must be in O(g(n)) and Ω(g(n)), so we only choose f(n) = O(n²) and f(n) = Ω(n²). Thus, f(n) = Θ(n²).

Determining The Complexity of Algorithm

From the above notations, actually there are still other notations like little-oh, little-omega, etc. However, in analysis algorithm Big Oh is often used since as I said it can guarantee the maximum performance of an algorithm.

When we’re talking about big oh of an algorithm, actually we’re talking about the complexity of that algorithm which explains how much the number of operations are affected as the input get larger. The complexity of an algorithm usually counted based on what statements are being used. Here are constant time for some statements.

1. Basic Operations (arithmetic, comparisons, accessing array’s elements, assignment) : The running time is always constant O(1)

Example :

read(x) // O(1)
a = 10; // O(1)
a = 1.000.000.000.000.000.000 // O(1)

2. If then else statement: Only taking the maximum running time from two or more possible statements.

Example:

age = read(x) // (1+1) = 2
if age < 17 then begin // 1
 status = "Not allowed!"; // 1
end else begin
 status = "Welcome! Please come in"; // 1
 visitors = visitors + 1; // 1+1 = 2
end;

So, the complexity of the above pseudo code is T(n) = 2 + 1 + max(1, 1+2) = 6. Thus, its big oh is still constant T(n) = O(1).

3. Looping (for, while, repeat): Running time for this statement is the number of looping multiplied by the number of operations inside that looping.

Example:

total = 0; // 1
for i = 1 to n do begin // (1+1)*n = 2n
 total = total + i; // (1+1)*n = 2n
end;
writeln(total); // 1

So, its complexity is T(n) = 1+4n+1 = 4n + 2. Thus, T(n) = O(n).

4. Nested Loop (looping inside looping): Since there is at least one looping inside the main looping, running time of this statement used O(n²) or O(n³).

Example:

for i = 1 to n do begin // (1+1)*n = 2n
 for j = 1 to n do begin // (1+1)n*n = 2n^2
 x = x + 1; // (1+1)n*n = 2n^2
 print(x); // (n*n) = n^2
 end;
end;

Common Running Time

There are some common running times when analyzing an algorithm:

1. O(1) – Constant Time
Constant time means the running time is constant, it’s not affected by the input size.

2. O(log n) – Logarithmic Time
Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.

3. O(n) – Linear Time
When an algorithm accepts n input size, it would perform n operations as well.

4.O(n log n) – Linearithmic Time
This running time is often found in “divide & conquer algorithms” which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm.

5. O(n²) – Quadratic Time
Look Bubble Sort algorithm!

6. O(n³) – Cubic Time
It has the same principle with O(n²).

7. O(2ⁿ) – Exponential Time
It is very slow as input get larger, if n = 1000.000, T(n) would be 2^1000.000. Brute Force algorithm has this running time.

8. O(n!) – Factorial Time
THE SLOWEST !!! Example : Travel Salesman Problem (TSP)

Closing Words

That’s all about simple theory about determining the complexity of an algorithm. I hope it can help you. Further reading, please refer a textbook from Thomas Cormen (Introduction to Algorithms, 2nd Edition), it was to be a huge help for me when learning about analyzing of algorithm. Good Luck 🙂

Leave a comment Cancel reply