Q-notation o Formal definition s(g(n), if t(n) is bounded below by some constant A function t(n) is said to be in 2(g(n), denoted t(n multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer no such that t(m)≥eg(n) for all n≥n D Exercises: prove the following using the above definition 10n2∈92(n2) 0.3n2-2n∈92(n2) 0.1n2∈(n2 Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-15Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-15 -notation Formal definition • A function t(n) is said to be in (g(n)), denoted t(n)  (g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that t(n)  cg(n) for all n  n0 Exercises: prove the following using the above definition • 10n 2  (n 2 ) • 0.3n 2 - 2n  (n 2 ) • 0.1n 3  (n 2 )