O'Reilly logo

Mobility Models for Next Generation Wireless Networks: Ad Hoc, Vehicular and Mesh Networks by Paolo Santi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Appendix B

Elements of Graph Theory, Asymptotic Notation, and Miscellaneous Notions

In this appendix, we start by introducing the asymptotic notation, and then report basic definitions and concepts from graph theory that have been used in this book. We will also formally define miscellaneous notions used in the book, such as linearity of operators, convexity and concavity, and so on. Most of the material presented in this appendix are based on Bollobàs (1985) and Bollobàs (1988), on Appendix B of Santi (2005), and on online resources such as Wikipedia and Wolfram MathWorld.

B.1 Asymptotic Notation

Definition B.1 (Big-O notation)
Let f(n) and g(n) be two functions defined on images/a02_I0001.gif. One can write f(n) = O(g(n)) if and only if there exist a positive real number c and a real number n0 such that

images/a02_I0002.gif

The big-O notation is used to express the fact that, as the argument n of the function grows larger, function f(n) is upper bounded by function g(n), up to a constant factor.

Definition B.2 (Big-Omega notation)
Let f(n) and g(n) be two functions defined on images/a02_I0003.gif. One can write f(n) = Ω(g(n)) if and only if there exist a positive real number c and a real number n0 such that

The big-Omega notation ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required