Rosen describes an algorithm as:
“An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.”
An algorithm can be expressed in a number of different ways however, it could be explained in plain English, written in a generic pseudocode (not a true programming language in itself, but a loose language system useful to describe algorithms in) or in a particular programming language.
All algorithms have the following characteristics in common:
- Input data. An algorithm will have input from a specified set
- Output data. From each input the algorithm will produce an output which is the solution to the problem in hand.
- Definiteness. All algorithms must be clearly and specifically defined to ensure there is no ambiguity.
- Correctness. All algorithms should produce the correct output from a given input.
- Finiteness. All algorithms should produce their output in a finite number of steps, the algorithm cannot go on infinitely.
- Effectiveness. All algorithms should produce their output in an efficient manner and in such a way that each step can be calculated finitely.
- Generalness. All algorithms should be able to support all different input ranges, not just a particular set of values.
Time Complexity
How long (much time) will it take for this algorithm to complete with this input value?
This question is related to the time-complexity of an algorithm, we express this in terms of the number of basic functions (such as addition, subtraction and comparison) required for the algorithm to complete. This means time complexity is independent of the specifics of a computer’s performance – and a separate calculation would be required to see how long an algorithm with input n of time complexity xn would take to execute on a computer Y.
Big-O notation is a way of comparing the growth function of different algorithms within particular bounds. This notation is defined as follows:
$$!
\begin{array}{l}
\mbox{Let } f \mbox{ and } g \mbox{ be functions from the set of integers or real numbers} \\
\mbox{ to the set of real numbers . We say that }f\left( x \right)\mbox{ is }O\left( {g\left( x \right)} \right)\\
\mbox{ if there are constants }C\mbox{ and }k\mbox{ such that:} \\ \\
\left| {f\left( x \right)} \right| \le C\left| {g\left( x \right)} \right|\mbox{ where }x > k \\
\end{array}
$$
The definition says that after a certain point, namely after k, the absolute value of f(x) is at most C times the absolute value of g(x). k and C are known as witnesses in this relationship – and only one pair of witnesses need be found to prove the relationship although infinite pairs will exist.
Some comments on big-O notation:
- $$ f\left( x \right) \mbox{ is } O\left( {g\left( x \right)} \right) $$ is often written as $$ f\left( x \right) = O\left( {g\left( x \right)} \right) $$ although this is not technically correct, $$ f\left( x \right) \in O\left( {g\left( x \right)} \right) $$ is the strictly correct notation.
- If $$ f\left( x \right) = O\left( {g\left( x \right)} \right) $$ and we know that $$ h\left( x \right) $$ has significantly larger absolute values than $$g\left( x \right) $$ for for sufficiently large values of x then it follows that $$ f\left( x \right) = O\left( {h\left( x \right)} \right) $$
- When it comes to polynomial functions, we can apply a general rule to simplify the notation:
$$!
\mbox{Let }f\left(x\right)=a_nx^2+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 \\
\mbox{ where } a_0,a_1,\ldots,a_{n-1},a_n \mbox{ are real numbers }\\
\mbox{Then } f\left(x\right) \mbox{ is } O\left(x^n\right)
$$
Example 1
Show that $$ 7x^2 \mbox{ is } O(x^3) $$
When $$ x > 7 $$, we can see that $$ 7x^2<x^3 $$. Consequentially, we can take $$ C=1 $$ and $$ k=7 $$ as witnesses to establish the relationship.
Example 2
Show that $$n^2 \mbox{ is not } O\left(n\right) $$
We need to show that no constants exist such that $$n^2 \le Cn \mbox{ where } n>k$$. To do this, we can simplify the inequality to $$n \le C $$ and from there we can see that no matter what the value of C is, it can never always be greater than n as n varies approaching infinity. As such, there is no big-O relation between the formulae.
References:
- FA-ADM – Slides 1 – University of Durham – Ioannis Ivrissimtzis – 2007
- FA-ADM – Slides 4 – University of Durham – Ioannis Ivrissimtzis – 2007
- Discrete Mathematics and Its Applications – Sixth Edition – Kenneth H. Rosen
