- #1
Nishiura_high
- 7
- 0
My textbook says O(3log2 n) can be written as O(nlog2 3). Why is that?
Thank you.
Thank you.
Big-Oh algebra with logarithms that I don't get?
- Thread starter Nishiura_high
- Start date
-
- Tags
- Algebra Logarithms
Click For Summary
SUMMARY
The discussion clarifies the equivalence of O(3log2 n) and O(nlog2 3) through logarithmic properties. Specifically, it utilizes the logarithmic identity that states log(a^b) = b * log(a). This allows the transformation of O(3log2 n) into O(nlog2 3) by recognizing that both expressions represent the same growth rate in Big-Oh notation. The key takeaway is understanding how logarithmic manipulation can simplify complexity expressions.
PREREQUISITES- Understanding of Big-Oh notation
- Familiarity with logarithmic properties
- Basic algebraic manipulation skills
- Knowledge of asymptotic analysis
- Study logarithmic identities in depth
- Learn about Big-Oh notation and its applications
- Explore examples of complexity transformations
- Investigate asymptotic analysis techniques
Students in computer science, software engineers, and anyone involved in algorithm analysis and performance optimization.
- #2
I like Serena
Science Advisor
Homework Helper
MHB
- 16,335
- 258
Welcome to PF, Nishiura_high! 
One of the log rules is that ##\log a^b = b \log a##.
So:
$$\log_2(3^{\log_2 n}) = \log_2 n \cdot \log_2 3$$
and also:
$$\log_2(n^{\log_2 3}) = \log_2 3 \cdot \log_2 n$$
Nishiura_high said:
One of the log rules is that ##\log a^b = b \log a##.
So:
$$\log_2(3^{\log_2 n}) = \log_2 n \cdot \log_2 3$$
and also:
$$\log_2(n^{\log_2 3}) = \log_2 3 \cdot \log_2 n$$
Similar threads
- · Replies 12 ·
- · Replies 12 ·
High School
Black Hole Entropy: Basis of Logarithm Explored
- · Replies 11 ·
- · Replies 3 ·
- · Replies 1 ·
High School
Why is pH a negative logarithm?
- · Replies 5 ·
Graduate
Question about branch of logarithm
- · Replies 2 ·
- · Replies 11 ·