Is lg(n) in Big Theta of ln(n) Due to the Change of Base Rule?

  • Context: Undergrad 
  • Thread starter Thread starter nanalala125
  • Start date Start date
  • Tags Tags
    Function
Click For Summary
SUMMARY

The discussion confirms that lg(n) is indeed in Θ(ln(n)) due to the change of base rule for logarithms. This rule states that the logarithm of n in any base can be expressed as a constant multiple of the logarithm of n in another base. Specifically, lg(n) can be rewritten as a constant times ln(n), establishing the relationship required for Big Theta notation.

PREREQUISITES
  • Understanding of logarithmic functions and their properties
  • Familiarity with Big Theta notation in algorithm analysis
  • Knowledge of the change of base rule for logarithms
  • Basic mathematical skills for manipulating logarithmic expressions
NEXT STEPS
  • Study the change of base formula for logarithms in detail
  • Learn about Big O, Big Omega, and Big Theta notations
  • Explore examples of logarithmic functions in algorithm complexity
  • Investigate the implications of logarithmic growth in computer science
USEFUL FOR

Students of computer science, mathematicians, and anyone involved in algorithm analysis or performance optimization will benefit from this discussion.

nanalala125
Messages
1
Reaction score
0
how to Show lg (n) є ɵ (ln n) ?

ɵ =big theta
 
Physics news on Phys.org
High nanalala. Do you know the "change of base rule" for logarithms? Basically it tells you that the log of n in any base is equal to a constant multiple of the log of n in any other base.

Can you see how to apply that to this problem?
 

Similar threads

MHB Yes, $2^{2^{2^n}}$ is a good example for $p(n)$ and $q(n)$ could be $n!$.
  • · Replies 13 ·
Replies
13
Views
3K
MHB Proving $T(n)=O(n^2 \lg^2 n)$ Using Recurrence Relation
  • · Replies 2 ·
Replies
2
Views
2K
Graduate When Does n lg n Switch from Ω to O?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to calculate expectation and variance of kernel density estimator?
  • · Replies 9 ·
Replies
9
Views
3K
MHB Solving T(n) = O(n lg n) using substitution method?
  • · Replies 2 ·
Replies
2
Views
2K
Determining the growth of two functions using Big-Oh definition
  • · Replies 7 ·
Replies
7
Views
1K
Graduate Proving variance with moment generating functions
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Order Comparison of Functions: f(n) < THETA(g(n)) for O(2^n) and O(3^n)
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad A Sequence T based on the Rule of Three
  • · Replies 15 ·
Replies
15
Views
2K
Undergrad How Can Bayes' Formula Help Understand Price Increases with Overseas Expansion?
  • · Replies 5 ·
Replies
5
Views
2K