Appendix N: Derivation of the Logarithm Change of Base Formula
We set out to prove the logarithm change of base formula: logb x = loga x loga b. To do so we let y = logb x and apply these as exponents on the base.
6.2 Properties of Logarithms
The proofs of the Change of Base formulas are a result of the other properties studied in this section. If we start with bx logb(a) and use the Power Rule
S&Z . & .
MATHEMATICS 0110A CHANGE OF BASE Suppose that we have
So we get the following rule: Change of Base Formula: logb a = logc a logc b. Example 1. Express log3 10 using natural logarithms. log3 10 =.
Change of Base
Derivation – Rules for Logarithms
Sometimes it is helpful to change the base of a logarithm such as logbn to a logarithm in base. Let x = logbn bx = n. - Def of log loga bx = loga n. - log of
DerivationRulesforLogarithms
Elementary Functions The logarithm as an inverse function
Each of these three properties is merely a restatement of a property of exponents. Smith (SHSU). Elementary Functions. 2013. 18 / 29. Changing the base.
. Logarithms (slides to )
Logarithms – University of Plymouth
Jan 16 2001 7. Quiz on Logarithms. 8. Change of Bases ... following important rules apply to logarithms. ... Proof that loga MN = loga M + loga N.
PlymouthUniversity MathsandStats logarithms
Introduction to Algorithms
I can prove this using the definition of big-Omega: This tells us that every positive power of the logarithm of n to the base b where b ¿ 1
cs lect fall notes
Lesson 5-2 - Using Properties and the Change of Base Formula
You can prove the Change of Base. Formula blog X x because exponents and logarithms are inverses. Take the log base a of both sides: log
What is a logarithm? Log base 10
Now we have a new set of rules to add to the others: Table 4. Functions of log base 10 and base e. Exponents. Log base 10. Natural Logs sr.
logarithms
Logarithms Math 121 Calculus II
Proof. By the inverse of the Fundamental Theorem of Calculus since lnx is defined as an In particular
logs
CS 5002: Discrete Structures Fall 2018
Lecture 9: November 8, 2018
1Instructors: Adrienne Slaughter, Tamara BonaciDisclaimer:These notes have not been subjected to the usual scrutiny reserved for formal publications.
They may be distributed outside this class only with the permission of the Instructor.Introduction to Algorithms
Readings for this week:
Rosen, Chapter 2.1, 2.2, 2.5, 2.6
Sets, Set Operations, Cardinality of Sets, Matrices9.1 OverviewObjective: Introduce algorithms.
1.Review logarithms
2.Asymptotic analysis
3.Dene Algorithm
4.Ho wto express or describ ean algorithm
5.Run time, space (Resource usage )
6.Determining Correctness
7.In troducerepresen tativeproblems
1. fo o9.2 Asymptotic Analysis
The goal with asymptotic analysis is to try to nd a bound, or an asymptote, of a function. This allows
us to come up with an \ordering" of functions, such that one function is denitely bigger than another,
in order to compare two functions. We do this by considering the value of the functions asngoes to innity, so for very large values ofn, as opposed to small values ofnthat may be easy to calculate. Once we have this ordering, we can introduce some terminology to describe the relationship of two functions. 9-19-2Lecture 9: November 8, 201823456781248163264128256512102420484096n!n
n2 nn2nlog(n)log(n)n
pn1Growth of Functions
From this chart, we see:
1lognpnnnlog(n)n22nn!nn(9.1)
ComplexityTerminology
(1)Constant (logn)Logarithmic (n)Linear (nlogn)Linearithmic nbPolynomial (bn) (whereb >1)Exponential (n!)Factorial9.2.1 Big-O: Upper BoundDenition 9.1 (Big-O: Upper Bound)f(n) =O(g(n))means there exists some constantcsuch
thatf(n)cg(n), for large enoughn(that is, asn! 1).We sayf(n) =O(g(n))
Example:I claim 3n2100n+ 6 =O(n2). I can prove this using the denition of big-O:Lecture 9: November 8, 20189-3
f(n) = 3n2100n+ 6 (9.2) g(n) =n2(9.3) )3n2100n+ 6cn2for somec(9.4)Ifc= 3 : 3n2100n+ 63n2(9.5)
To prove using Big-O:
Determinef(n) andg(n)
Write the equation based on the denition
Choose acsuch that the equation is true.
{If you can nd ad, thenf(n) =O(g(n)). If not, thenf(n)6=O(g(n)).These statements are all true:
3n2100n+ 6 =O(n2) (9.6)
3n2100n+ 6 =O(n3) (9.7)
3n2100n+ 66=O(n) (9.8)
Proving
9.7 f(n) = 3n2100n+ 6 (9.9) g(n) =n3(9.10) )3n2100n+ 6 =cn3(for somec) (9.11)Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.12)
We also know this to be true because order istransitive: iff(n) =O(g(n)), andg(n) =O(h(n)), then f(n) =O(h(n)). Sincen2=O(n3), then anyf(n) =O(n2) is alsoO(n3).Proving
9.8 f(n) = 3n2100n+ 6 (9.13) g(n) =n(9.14)For anyc:cn <3n2(whenn > c) (9.15)
9.2.2 Big-Omega: Lower BoundDenition 9.2 (Big-Omega: Lower Bound)f(n) =
(g(n))means there exists some constantc such thatf(n)cg(n), for large enoughn(that is, asn! 1).We sayf(n) =
(g(n))or \fofnis Big Omega ofgofn"9-4Lecture 9: November 8, 2018
Example:I claim 3n2100n+ 6 =
(n2). I can prove this using the denition of big-Omega: f(n) = 3n2100n+ 6 (9.16) g(n) =n2(9.17) )3n2100n+ 6cn2for somec(9.18)Ifc= 2 : 3n2100n+ 62n2(9.19)
We show Big-Omega the same way we show Big-O.
These statements are all true:
3n2100n+ 6 =
(n2) (9.20)3n2100n+ 66=
(n3) (9.21)3n2100n+ 6 =
(n) (9.22)Proving
9.21 f(n) = 3n2100n+ 6 (9.23) g(n) =n3(9.24) )3n2100n+ 6cn3(for somec) (9.25)Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.26)
Proving
9.22 f(n) = 3n2100n+ 6 (9.27) g(n) =n(9.28)For anyc:cn <3n2(whenn >100c) (9.29)
9.2.3 Big-Theta: \Tight" BoundDenition 9.3 (Big-Theta: \Tight" Bound)f(n) = (g(n))means there exists some constantsc1
andc2such thatf(n)c1g(n)andf(n)c2g(n).We sayf(n) = (g(n))or \fofnis Big-Theta ofgofn".
Denition 9.4 (Theta and \order of")Whenf(x) = (g(x)), it is the same as sayingf(x)is the order ofg(x), or thatf(x)andg(x)are the same order.3n2100n+ 6 = (n2)Both Oand
applyLecture 9: November 8, 20189-5
3n2100n+ 66= (n3)Only Oapplies
3n2100n+ 66= (n)Only
app lies Interesting AsideDonald Knuth popularized the use of Big-O notation. It was originally inspired by the use of \ell" numbers, written asL(5), which indicates a number that we don't know the exactvalue of, but is less than 5. That allows us to reason about the value without knowing the exact value:
we knowL(5)<100, for example. Theorem 9.5Iff(x) =anxn+an1xn1++a1x+a0, thenf(x) =O(n) a)f(x) = 17x+ 11 b)f(x) =x2+ 1000 c)f(x) =xlogxd)f(x) =x4=2 e)f(x) = 2xf)f(x) =bxc dxe9.2.4 Logs, Powers, Exponents
We've seenf(n) =O(nd). Ifd > c >1, thennc=O(nc).ncisOnd;butndis notO(nc). log bnisO(n) wheneverb >1. Wheneverb >1, c and d are positive: (log bn)cisOnd;butndis not (O(logbn)c) (9.30)This tells us that every positive power of the logarithm of n to the base b, where b > 1, is big-O of every
positive power of n, but the reverse relationship never holds. In Example 7, we also showed that n is
O(2n). More generally, whenever d is positive and b > 1, we have n disO(bn);butbnis notOnd(9.31)This tells us that every power of n is big-O of every exponential function of n with a base that is greater
than one, but the reverse relationship never holds. Furthermore, we have when c > b > 1, b nisO(cn) butcnis notO(bn) (9.32)This tells us that if we have two exponential functions with dierent bases greater than one, one of these
functions is big-O of the other if and only if its base is smaller or equal.9.2.5 Adding Functions
There are a set of rules that govern combining functions together.O(f(n)) +O(g(n))!O(max(f(n);g(n))) (9.33)
(f(n)) + (g(n))! (max(f(n);g(n))) (9.34) (f(n)) + (g(n))!(max(f(n);g(n)) (9.35) These statements express the notion that the largest term of the statement is the dominant one. For example,n3+ 2n2+ 3 =O(n3).Example:Prove thatn2=O(2n).
9-6Lecture 9: November 8, 2018Example:Prove that iff1(n) =O(g1(n)) andf2(n) =O(g2(n)), thenf1(n)+f(n) =O(g1(n)+g2(n)).Example:
f(n) =n+ logn(9.36) g(n) =p(n) (9.37)Isf(n) =O(g(n)),g(n) =O(f(n)), or both?Example:Iff(n) =n+ logn+pn, nd a simple functiongsuch thatf(n) = (g(n)).
Lecture 9: November 8, 20189-7Summary
f(n) =O(g(n)) meanscg(n) is an upper bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for large enoughn(i.e.,nn0for some constantn0). f(n) = (g(n)) meanscg(n) is a lower bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for allnn0. f(n) = (g(n)) meansc1g(n) is an upper bound onf(n) andc2g(n) is a lower bound onf(n), for allnn0. Thus there exist constantsc1 andc2 such thatf(n)c1g(n) andf(n)c2g(n). This means thatg(n) provides a nice, tight bound onf(n).9.2.6 Introduction to Algorithms
Analgorithmis a set of instructions for accomplishing a task.Technically, any program is an algorithm
We talk about algorithms as general approaches to specic problems An algorithm isgeneral, but isimplementedin code to make it specicAlgorithms are like Recipes
If I were to use a simile, I'd say algorithms are like recipes. People have been cooking and baking for a looong time {Let's take advantage of solved problems and use them as starting blocks There are general approaches to dierent kinds of foods Each recipe for a chocolate chip cookie is a little dierent, but follows the same general structure. I can adapt a recipe for chocolate chip cookies to a dierent kind of cookie if I want. I might modify my recipe depending on the context I'm cooking in: cooking for a 200 person formal dinner versus playing around on a Saturday afternoon.What is an algorithm?
An algorithm is the part of the \recipe" that stays the same no matter what it's implemented inCS 5002: Discrete Structures Fall 2018
Lecture 9: November 8, 2018
1Instructors: Adrienne Slaughter, Tamara BonaciDisclaimer:These notes have not been subjected to the usual scrutiny reserved for formal publications.
They may be distributed outside this class only with the permission of the Instructor.Introduction to Algorithms
Readings for this week:
Rosen, Chapter 2.1, 2.2, 2.5, 2.6
Sets, Set Operations, Cardinality of Sets, Matrices9.1 OverviewObjective: Introduce algorithms.
1.Review logarithms
2.Asymptotic analysis
3.Dene Algorithm
4.Ho wto express or describ ean algorithm
5.Run time, space (Resource usage )
6.Determining Correctness
7.In troducerepresen tativeproblems
1. fo o9.2 Asymptotic Analysis
The goal with asymptotic analysis is to try to nd a bound, or an asymptote, of a function. This allows
us to come up with an \ordering" of functions, such that one function is denitely bigger than another,
in order to compare two functions. We do this by considering the value of the functions asngoes to innity, so for very large values ofn, as opposed to small values ofnthat may be easy to calculate. Once we have this ordering, we can introduce some terminology to describe the relationship of two functions. 9-19-2Lecture 9: November 8, 201823456781248163264128256512102420484096n!n
n2 nn2nlog(n)log(n)n
pn1Growth of Functions
From this chart, we see:
1lognpnnnlog(n)n22nn!nn(9.1)
ComplexityTerminology
(1)Constant (logn)Logarithmic (n)Linear (nlogn)Linearithmic nbPolynomial (bn) (whereb >1)Exponential (n!)Factorial9.2.1 Big-O: Upper BoundDenition 9.1 (Big-O: Upper Bound)f(n) =O(g(n))means there exists some constantcsuch
thatf(n)cg(n), for large enoughn(that is, asn! 1).We sayf(n) =O(g(n))
Example:I claim 3n2100n+ 6 =O(n2). I can prove this using the denition of big-O:Lecture 9: November 8, 20189-3
f(n) = 3n2100n+ 6 (9.2) g(n) =n2(9.3) )3n2100n+ 6cn2for somec(9.4)Ifc= 3 : 3n2100n+ 63n2(9.5)
To prove using Big-O:
Determinef(n) andg(n)
Write the equation based on the denition
Choose acsuch that the equation is true.
{If you can nd ad, thenf(n) =O(g(n)). If not, thenf(n)6=O(g(n)).These statements are all true:
3n2100n+ 6 =O(n2) (9.6)
3n2100n+ 6 =O(n3) (9.7)
3n2100n+ 66=O(n) (9.8)
Proving
9.7 f(n) = 3n2100n+ 6 (9.9) g(n) =n3(9.10) )3n2100n+ 6 =cn3(for somec) (9.11)Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.12)
We also know this to be true because order istransitive: iff(n) =O(g(n)), andg(n) =O(h(n)), then f(n) =O(h(n)). Sincen2=O(n3), then anyf(n) =O(n2) is alsoO(n3).Proving
9.8 f(n) = 3n2100n+ 6 (9.13) g(n) =n(9.14)For anyc:cn <3n2(whenn > c) (9.15)
9.2.2 Big-Omega: Lower BoundDenition 9.2 (Big-Omega: Lower Bound)f(n) =
(g(n))means there exists some constantc such thatf(n)cg(n), for large enoughn(that is, asn! 1).We sayf(n) =
(g(n))or \fofnis Big Omega ofgofn"9-4Lecture 9: November 8, 2018
Example:I claim 3n2100n+ 6 =
(n2). I can prove this using the denition of big-Omega: f(n) = 3n2100n+ 6 (9.16) g(n) =n2(9.17) )3n2100n+ 6cn2for somec(9.18)Ifc= 2 : 3n2100n+ 62n2(9.19)
We show Big-Omega the same way we show Big-O.
These statements are all true:
3n2100n+ 6 =
(n2) (9.20)3n2100n+ 66=
(n3) (9.21)3n2100n+ 6 =
(n) (9.22)Proving
9.21 f(n) = 3n2100n+ 6 (9.23) g(n) =n3(9.24) )3n2100n+ 6cn3(for somec) (9.25)Ifc= 1 : 3n2100n+ 6n3(whenn >3) (9.26)
Proving
9.22 f(n) = 3n2100n+ 6 (9.27) g(n) =n(9.28)For anyc:cn <3n2(whenn >100c) (9.29)
9.2.3 Big-Theta: \Tight" BoundDenition 9.3 (Big-Theta: \Tight" Bound)f(n) = (g(n))means there exists some constantsc1
andc2such thatf(n)c1g(n)andf(n)c2g(n).We sayf(n) = (g(n))or \fofnis Big-Theta ofgofn".
Denition 9.4 (Theta and \order of")Whenf(x) = (g(x)), it is the same as sayingf(x)is the order ofg(x), or thatf(x)andg(x)are the same order.3n2100n+ 6 = (n2)Both Oand
applyLecture 9: November 8, 20189-5
3n2100n+ 66= (n3)Only Oapplies
3n2100n+ 66= (n)Only
app lies Interesting AsideDonald Knuth popularized the use of Big-O notation. It was originally inspired by the use of \ell" numbers, written asL(5), which indicates a number that we don't know the exactvalue of, but is less than 5. That allows us to reason about the value without knowing the exact value:
we knowL(5)<100, for example. Theorem 9.5Iff(x) =anxn+an1xn1++a1x+a0, thenf(x) =O(n) a)f(x) = 17x+ 11 b)f(x) =x2+ 1000 c)f(x) =xlogxd)f(x) =x4=2 e)f(x) = 2xf)f(x) =bxc dxe9.2.4 Logs, Powers, Exponents
We've seenf(n) =O(nd). Ifd > c >1, thennc=O(nc).ncisOnd;butndis notO(nc). log bnisO(n) wheneverb >1. Wheneverb >1, c and d are positive: (log bn)cisOnd;butndis not (O(logbn)c) (9.30)This tells us that every positive power of the logarithm of n to the base b, where b > 1, is big-O of every
positive power of n, but the reverse relationship never holds. In Example 7, we also showed that n is
O(2n). More generally, whenever d is positive and b > 1, we have n disO(bn);butbnis notOnd(9.31)This tells us that every power of n is big-O of every exponential function of n with a base that is greater
than one, but the reverse relationship never holds. Furthermore, we have when c > b > 1, b nisO(cn) butcnis notO(bn) (9.32)This tells us that if we have two exponential functions with dierent bases greater than one, one of these
functions is big-O of the other if and only if its base is smaller or equal.9.2.5 Adding Functions
There are a set of rules that govern combining functions together.O(f(n)) +O(g(n))!O(max(f(n);g(n))) (9.33)
(f(n)) + (g(n))! (max(f(n);g(n))) (9.34) (f(n)) + (g(n))!(max(f(n);g(n)) (9.35) These statements express the notion that the largest term of the statement is the dominant one. For example,n3+ 2n2+ 3 =O(n3).Example:Prove thatn2=O(2n).
9-6Lecture 9: November 8, 2018Example:Prove that iff1(n) =O(g1(n)) andf2(n) =O(g2(n)), thenf1(n)+f(n) =O(g1(n)+g2(n)).Example:
f(n) =n+ logn(9.36) g(n) =p(n) (9.37)Isf(n) =O(g(n)),g(n) =O(f(n)), or both?Example:Iff(n) =n+ logn+pn, nd a simple functiongsuch thatf(n) = (g(n)).
Lecture 9: November 8, 20189-7Summary
f(n) =O(g(n)) meanscg(n) is an upper bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for large enoughn(i.e.,nn0for some constantn0). f(n) = (g(n)) meanscg(n) is a lower bound onf(n). Thus there exists some constantcsuch thatf(n) is alwayscg(n), for allnn0. f(n) = (g(n)) meansc1g(n) is an upper bound onf(n) andc2g(n) is a lower bound onf(n), for allnn0. Thus there exist constantsc1 andc2 such thatf(n)c1g(n) andf(n)c2g(n). This means thatg(n) provides a nice, tight bound onf(n).9.2.6 Introduction to Algorithms
Analgorithmis a set of instructions for accomplishing a task.Technically, any program is an algorithm
We talk about algorithms as general approaches to specic problems An algorithm isgeneral, but isimplementedin code to make it specicAlgorithms are like Recipes
If I were to use a simile, I'd say algorithms are like recipes. People have been cooking and baking for a looong time {Let's take advantage of solved problems and use them as starting blocks There are general approaches to dierent kinds of foods Each recipe for a chocolate chip cookie is a little dierent, but follows the same general structure. I can adapt a recipe for chocolate chip cookies to a dierent kind of cookie if I want. I might modify my recipe depending on the context I'm cooking in: cooking for a 200 person formal dinner versus playing around on a Saturday afternoon.What is an algorithm?
An algorithm is the part of the \recipe" that stays the same no matter what it's implemented in- log base change formula proof
- log base change rule proof
- logarithm base change formula proof