FIU COT 5407 - Growth Rates (23 pages)

Previewing pages 1, 2, 22, 23 of 23 page document
View Full Document

Growth Rates

Previewing pages 1, 2, 22, 23 of actual document.

View Full Document
View Full Document

Growth Rates

122 views

Lecture Notes

Pages:
23
School:
Florida International University
Course:
Cot 5407 - Introduction to Algorithms
Introduction to Algorithms Documents
• 51 pages

• 26 pages

• 15 pages

• 87 pages

• 13 pages

• 29 pages

• 38 pages

• 18 pages

• 14 pages

• 23 pages

• 33 pages

• 15 pages

• 31 pages

• 32 pages

• 13 pages

• 26 pages

• 2 pages

• 12 pages

• 14 pages

• 2 pages

• 26 pages

• 36 pages

• 50 pages

• 16 pages

• 32 pages

• 12 pages

• 28 pages

• 46 pages

• 23 pages

• 14 pages

• 16 pages

Unformatted text preview:

Growth Rates Linear n Quadratic n2 Cubic n3 T n Growth rates of functions In a log log chart the slope of the line corresponds to the growth rate of the function 1E 30 1E 28 1E 26 1E 24 1E 22 1E 20 1E 18 1E 16 1E 14 1E 12 1E 10 1E 8 1E 6 1E 4 1E 2 1E 0 1E 0 Cubic Quadratic Linear 1E 2 Analysis of Algorithms 1E 4 1E 6 1E 8 1E 10 n 1 Constant Factors The growth rate is not affected by constant factors or lower order terms Examples T n 102n 105 is a linear function 105n2 108n is a quadratic function 1E 26 1E 24 1E 22 1E 20 1E 18 1E 16 1E 14 1E 12 1E 10 1E 8 1E 6 1E 4 1E 2 1E 0 1E 0 Quadratic Quadratic Linear Linear 1E 2 1E 4 1E 6 1E 8 1E 10 n Analysis of Algorithms 2 Big Oh Notation 10 000 Given functions f n and g n we say that 1 000 f n is O g n if there are positive constants 100 c and n0 such that 3n 2n 10 n f n cg n for n n0 Example 2n 10 is O n 2n 10 cn c 2 n 10 n 10 c 2 Pick c 3 and n0 10 10 1 1 Analysis of Algorithms 10 n 100 1 000 3 Big Oh Example 1 000 000 Example the function n2 is not O n n 2 100n 100 000 10n n 10 000 n2 cn 1 000 n c The above 100 inequality cannot be satisfied since c 10 must be a constant 1 1 Analysis of Algorithms 10 n 100 1 000 4 More Big Oh Examples 7n 2 7n 2 is O n need c 0 and n0 1 such that 7n 2 c n for n n0 this is true for c 7 and n0 1 3n3 20n2 5 3n3 20n2 5 is O n3 need c 0 and n0 1 such that 3n3 20n2 5 c n3 for n n0 is true c 4log and n n0 21 this 3 log n for log 3 log n log log n is O log n need c 0 and n0 1 such that 3 log n log log n c log n for n n0 Algorithms this is true for c 4 Analysis and n0of 2 5 Big Oh and Growth Rate The big Oh notation gives an upper bound on the growth rate of a function The statement f n is O g n means that the growth rate of f n is no more than the growth rate of g n We can use the big Oh notation to rank functions according to their growth rate f n is O g n g n is O f n g n grows more Yes No f n grows more No Yes Same growth

View Full Document

Unlocking...