《548-bender.pdf-1.3 Typical Functions》.pdfVIP

Introduction and Asymptotic Notation 1.2.1 Secondary goals • Learn proof techniques • Learn some mathematics • Have fun: Algorithms can be beautiful and ever poetic. 1.3 Typical Functions 1 2 10 k 2 • polynomials – n, n , n , n , n , etc (grows fast) n n n 2n • exponentials – 2 , 3 , e , 11 , etc (grows very fast) • logarithms – log n = log n, ln n, log n, etc (grows slowly) 2 10 • poly logarithms – (log n)2 (grows slowly) • log-logarithmic – log log n (grows slowly) ∗ • log n – the number of times you have to take the log of a number before you get something less than 1. (grows very slowly) ∗ 1.3.1 Illustrating the Growth of log log n and log n • Given: Let N be the number of particles in the Universe. It is estimated that there are over 1080 particles in the universe. 1. Question: What is the loglog of that number? – Answer: We know that 103 ≈ 210. This means that 1080 can be represented as 103(27), which is about 2270. The log2270 ≈ 270 and the loglog2270 is about 8.1. 2. Question: What is the log∗ of that number? ∗ 80 – Answer: 5 ≤ log (10 ) ≤ 6 ∗ Moral: loglog n and log n are very slowly growing functions. 22 Introduction and Asymptotic Notation 1.4 Review of logs Here are some basic properties of logs: • log x = y ⇐⇒ x = ay a • log x = y a •