O-notation o Formal definition A function t(n) is said to be in o((), denoted t(n) o(gn), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n,i.e, if there exist some positive constant cl and cz and some nonnegative integer no such that 2g(n)≤tmn)≤cng(n) for all n≥no D Exercises: prove the following using the above definition 10n2∈o(m2) 0.3n2-2mn∈⊙(m2) (1/2)m(n+1)∈⊙(m2) Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-16Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-16 -notation Formal definition • A function t(n) is said to be in (g(n)), denoted t(n)  (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some nonnegative integer n0 such that c2 g(n)  t(n)  c1 g(n) for all n  n0 Exercises: prove the following using the above definition • 10n 2  (n 2 ) • 0.3n 2 - 2n  (n 2 ) • (1/2)n(n+1)  (n 2 )