Desktop version

Home arrow Engineering

  • Increase font
  • Decrease font


<<   CONTENTS   >>

Big O (O)

In computer science, big О notation is used to understand algorithms on how their running time or space requirements grow with increases in input size. It is typically used to provide an upper bound on the growth rate of the function. The big О notation gives us the upper bound idea, which is typically used to represent the time and space complexity of an algorithm. In the following, we formally define the big О notation.

Definition 12.1 Let f(n) and g(n) be two non-negative increasing functions, shown in Fig. 12.1. A function f(n) = 0(g(n)) if there are constants, which are c(> 0) and «о > 0, such that 0 < f(n) < cg(n), for all n > no.

In the following, we classify algorithms from the best-to-worst performance in terms of big О notation. A logarithmic algorithm—O(logn); runtime grows logarithmically in proportion to n. A linear algorithm—0{rt) runtime grows di-

Big О notation

Figure 12.1: Big О notation.

rectly in proportion to n. A superlinear algorithm—0(nogn); runtime grows in proportion to n. A polynomial algorithm—0(nc); runtime grows quicker than previous all based on n. An exponential algorithm—0(c"); runtime grows even faster than a polynomial algorithm based on n. A factorial algorithm—0{n) runtime grows the fastest and becomes quickly unusable for even small values of n. Some of the examples of all those types of algorithms are mentioned as follows. Logarithmic algorithm—O(logn)—binary search. Linear algorithm— 0{n)—linear search. Superlinear algorithm—0{n log/г)—heap sort and merge sort. Polynomial algorithm—0(nc)—strassen’s matrix multiplication, bubble sort, selection sort, insertion sort, and bucket sort. Exponential algorithm— 0(cn)—tower of Hanoi. Factorial algorithm—0(n)—determinant expansion by minors, and brute force search algorithm for the traveling salesman problem.

We provide an example for each type of algorithm considered above. Binary search—find a particular number from a list of given integer numbers that are sorted. Linear search—find a particular number from a list of given integer numbers that are unsorted. Merge sort—divide an unsorted list into sublists, each of which contains one element (a list of one element is considered sorted), and then repeatedly merge a pair of sublists to provide a new sorted sublist until there is only one sublist remaining. Strassen’s matrix multiplication—given two square matrices A and В of size nxn each, find their multiplication matrix. Tower of Hanoi—given a game board with three pegs and a set of disks of different diameters that are stacked from the smallest to the largest on the leftmost peg, move all the disks to the rightmost peg following the two rules, which are (i) only one disk is moved at a time and (ii) a larger diameter disk is not placed on a smaller disk. Brute force search algorithm for the traveling salesman problem—given a list of cities and the distances between each pair of cities, what is the shortest possible route (optimum solution) that visits each city and returns to the origin city.

Theorem 12.1

100/; + 10000 is in 0(n).

Proof 12.1 We select no = 1 and c = 10100,Vn > no.

100/; + 10000 < lOOn + lOOOOn as n > 1 = 10100/;

= cn

Thus, by definition of big О, 1 OOn + 10000 is in 0(n). U

Big Omega (Ω)

Big £1 notation provides an asymptotic lower bound. Note that the best case performance of an algorithm is typically not useful. Therefore, big £1 notation is the least used notation among all three notations. In the following, we formally define the big £1 notation.

Definition 12.2 Let f(n) and g(n) be two non-negative increasing functions, shown in Fig. 12.2. A function f(n) = £l(g(n)) if there are constants, which are c(> 0) and no > 0, such that 0 < cg(n) < /(n), for all n > пц.

Big П notation

Figure 12.2: Big П notation.

Theorem 12.2

3 — In + 1 is in £2(/j3).

Proof 12.2 We select no = 3 and с = 1, Vn > /?o- 2и3In + 1 = и3 + (и3 — 7л) + 1 as и > 3

>пъ

= C/J3

Thus, by definition of big 12, 2n3 — 7n + 1 is in 12(/r3). ■

Big Theta (Θ)

The big © notation bounds a function from above and below, so it defines exact asymptotic behavior. In other words, to prove big © notation, just prove both big О and big П, separately. The big © notation gives us the average case idea. In the following, we formally define the big © notation.

Definition 12.3 Let f(n) and g(n) be two non-negative increasing functions, shown in Fig. 12.3. A function f(n) = @(g(n)) if there are constants, which are C| (> 0), cj{> 0), and пц > 0, such that 0 < cjg(n) < f(n) < C2g(n), for all n > пц.

Big 0 notation

Figure 12.3: Big 0 notation.

Theorem 12.3

2n3 7n + 1 is in ©(n3).

Proof 12.3 Theorem 12.2 proved that 2/r3In + 1 is in f2(n3), when no = 3 and ci = 1. To check the upper bound, we consider the following.

We select «о = 1 and c-2 = 3,Vn > no.

2n3 — 7n -F 1 < 2n3 + n3 as n > 1 = 3 n3

= С2И3

By definition of big O, 2и3 -7n + 1 is in 0(n3).

Therefore, by definition of big ®, 2n3 -7n + 1 is in ®(n3). ■

 
<<   CONTENTS   >>

Related topics