D Asymptotic Behavior of Functions

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Appendix D
Asymptotic Behavior of Functions

Asymptotic functions or notations are used to represent the growth rate of functions which are necessary in many applications in computing, communications, networking, and signal processing. Asymptotic notations represent certain characteristics of growth functions. They are also called order notations or Landau’s notations. One of the most relevant applications is estimation of computational time complexity of algorithms. In fact, for any algorithm, the resource requirements, such as time taken to complete the execution, amount of memory required for operation, or number of messages to be exchanged for functioning, can be represented as a mathematical function. Usually, such functions are represented in terms of the input size (n) where input can be the number of items to be processed by an algorithm or the number of nodes in a network. Once the resource required is estimated as a function, its growth rate can be represented using the asymptotic notations. The three most widely used notations, Big Oh ( $𝒪 (\cdot)$ $? (\cdot)$ ), Big Omega ( $Ω (\cdot)$ $Ω (\cdot)$ ), and Big Theta ( $Θ (\cdot)$ $Θ (\cdot)$ ), are briefly presented in this appendix.

D.1 Big Oh ( $𝒪 (\cdot)$ $? (\cdot)$ ) Notation

Big Oh ( $𝒪$ $?$ ) notation is one of the popularly used asymptotic notations. $𝒪 (\cdot)$ $? (\cdot)$ captures the upper bound of a growth function, such as the representation of time complexity of an algorithm, as a function of the input size or the resources required for the operation of a system.

For a given function, f (n), if there exist positive real numbers c > 0 and n₀ such that for all values of n > n₀, f (n) ≤ cg(n), then it can be represented as $f (n) = 𝒪 (g (n))$ $f (n) = ? (g (n))$ . That is, the function g(n) can be considered as an upper bound of the given function f (n) as the value of n grows larger. For example, a network algorithm that takes an execution time of f (n) = 5n² + 3n + 34 can be said to be of $𝒪 (n^{2})$ $? (n^{2})$ . An algorithm that takes a constant amount of time irrespective of the input size is said to be of constant time complexity, represented as $𝒪 (1)$ $? (1)$ . For example, for a cellular base station that broadcasts a message to all n mobile devices in the network, the number of transmissions required for message transmissions, typically known as message complexity, can be said to be $𝒪 (1)$ $? (1)$ because message complexity is independent of the number of mobile devices that exist in the network. When considering, in the same example, the number of unicast transmissions to the mobile devices, one can find that the message complexity can be $𝒪 (n)$ $? (n)$ .

Figure D.1 shows a graphical representation of $𝒪$ $?$ notation.

A graph of running time versus n shows two curves representing the functions "g of n" and "f of n." The "f of n" curve, after an initial raise, drops and runs below the "g of n" curve. Both curves are shown to increase with n. The point of intersection of the curves corresponds to value n subscript 0 on the horizontal axis.

Figure D.1. A graphical representation of Big Oh ( $𝒪$ $?$ ) notation

D.2 Big Omega ( $Ω (\cdot)$ $Ω (\cdot)$ ) Notation

For a given function, f (n), if there exist positive real numbers c > 0 and n₀ such that for all values of n > n₀, f (n) ≥ cg(n), then it can be represented as f (n) = Ω(g(n)). That is, the function g(n) can be considered as a lower bound of the given function f (g). For example, a network algorithm that takes an execution time of f (n) = 5n² + 3n + 34 can be said to be of either Ω(n²) or Ω(n). Of these two lower bounds, the tighter lower bound is Ω(n²). Figure D.2 shows a graphical representation of Ω(·) notation.

A graph of running time versus n shows two curves representing the functions "g of n" and "f of n." The "f of n" curve, after an initial raise, drops and increases steadily. The "g of n" curve (also increasing steadily) runs below it. A a line at the value n subscript 0 on the horizontal axis intersects both curves.

Figure D.2. A graphical representation of Big Omega (Ω) notation

D.3 Big Theta ( $Θ (\cdot)$ $Θ (\cdot)$ ) Notation

For a given function, f (n), if there exist positive real numbers c₁, c₂ > 0, and n₀ such that for all values of n > n₀, c₁g(x) ≤ f (n) ≤ c₂g(n), then it can be represented as $f (n) = Θ (g (n))$ $f (n) = Θ (g (n))$ . That is, the function g(n) can be considered both as an upper as well as a lower bound of the given function f (n). Therefore, the Θ(·) notation is used to represent tight bound.

Figure D.3 shows a representation of Θ(·) notation. Consider the same example we mentioned in the previous sections of a network algorithm that takes an execution time of f (n) = 5n² + 3n + 34. Since the algorithm’s upper and lower bounds, respectively, are $𝒪 (n^{2})$ $? (n^{2})$ and Ω(n²), it can be said to be Θ(n²), which is a very tight bound.

Figure shows a graph representing three functions.

Figure D.3. A graphical representation of Big Theta (Θ) notation

Readers can refer to more details on asymptotic notations, algorithmic time complexities, and algorithm design in [20].

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for D Asymptotic Behavior of Functions

Create new playlist

Sign In

Sign Up

Appendix DAsymptotic Behavior of Functions

D.1 Big Oh (O(⋅)?(⋅)<math alttext="" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mstyle mathvariant="script"><mi>?</mi></mstyle><mo stretchy="false" form="prefix">(</mo><mo>⋅</mo><mo stretchy="false" form="postfix">)</mo></mrow></math>) Notation

D.2 Big Omega (Ω(⋅)Ω(⋅)<math alttext="" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mi>Ω</mi><mo stretchy="false" form="prefix">(</mo><mo>⋅</mo><mo stretchy="false" form="postfix">)</mo></mrow></math>) Notation

D.3 Big Theta (Θ(⋅)Θ(⋅)<math alttext="" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mi>Θ</mi><mo stretchy="false" form="prefix">(</mo><mo>⋅</mo><mo stretchy="false" form="postfix">)</mo></mrow></math>) Notation

Table of Contents for
D Asymptotic Behavior of Functions

Appendix D
Asymptotic Behavior of Functions

D.1 Big Oh ( $𝒪 (\cdot)$ $? (\cdot)$ ) Notation

D.2 Big Omega ( $Ω (\cdot)$ $Ω (\cdot)$ ) Notation

D.3 Big Theta ( $Θ (\cdot)$ $Θ (\cdot)$ ) Notation