[next] [prev] [prev-tail] [tail] [up]

Part 3
Algorithm

Knowledge Base

Overview

An algorithm is a sequence of problem-solving steps that takes some sets of values as inputs, and produces some set of values as output. Therefore, an algorithm is said to be correct, if for any input sets, it produces the correct output set.

When a huge computer program is developed, there is a need to determine how ’quickly’ this program is to perform and to accomplish a number of tasks. This running time of an algorithm on a particular set of inputs indicates the number of operation or step executed. In general, people are interested in the study on the worst-case performance of the computation, usually referred as the complexity of the algorithm. Most of the time, we are not interested in the actual function that describes the time complexity, but the complexity class, which tells us a great deal about the growth of the complexity function. In other words, we want to know how the running time of an algorithm increases in terms of the size of the input.

Asymptotic Upper Bound

This algorithmic complexity is generally written in a form known as Big-O notation, where the O represents the upper bound of complexity of the algorithm, and a value n represents the size of the set the algorithm runs against. In other words, this complexity class, f(n), represents the worst-case performance of the function, g(n). Mathematically, we can define as following:

O(g(n)) = {f(n)∥∃c > 0,∃N > 0,s.t.,0 ≤ f(n) ≤ c ⋅g(n),∀n ≥ N}
(3.6.6)

There is a function f(n)) that is O(g(n)), such that for any value of n, no matter what particular input size of n is chosen, the running time on that input is bounded from above by the value of f(n).

Asymptotic Lower Bound

Similar to the asymptotic upper bound provided by O-notation, the asymptotic lower bound can be found using Ω-notation. In general, the complexity class bounded by the Ω indicates the best-case performance of the complexity function. Mathematically, we can define as following:

Ω(g(n)) = {f(n)∥∃c > 0,∃N > 0,s.t.,0 ≤ c⋅g(n) ≤ f(n),∀n ≥ N}
(3.6.7)

No matter what particular input of size n is chosen, for each value of n, the running time on that input is at least a constant times g(n), for sufficiently large n.

Common Complexity Class

Most of the time, we are more interested in the worst-case performance, or average-case analysis. Hence, in algorithmic perspective, an algorithm is said to have a running time of O(g(n)), for all inputs; or Ω(g(n)) complexity, for some inputs. Here is the list below of commonly seen complexity classes:

Complexity Function f(n) n = 2  n = 210 
1 1 1
log log (n) >>0 3.32
log (n) 1 10
n 2 210
n ⋅ log (n) 2 10 ⋅ 210
n2 4 220
n3 8 230
n! 2 1024!
2n 4 21024
For instance, O(n) means an algorithm has a linear complexity for any value of n. Then, it takes ten times longer to operate on a set of 10 items than it does on a set of 1 item. Similarly, if the algorithm had a complexity of O(n2), known as quadratic complexity, then it would take a hundred times longer to operate on a set of 10 items than it does on a set of 1 item.

Space Complexity

In many algorithm, we need a certain amount of extra memory space to perform the operations. An algorithm is called in-place, if constant space is necessary to produce the output, and vice versa.

[next] [prev] [prev-tail] [front] [up]