Proving the Log of a Power Rule: log(n^k) is O(log(n)) for any constant k > 0

  • Thread starter Thread starter Gear2d
  • Start date Start date
AI Thread Summary
To prove that log(n^k) is O(log(n)) for any constant k > 0, one can start with the logarithmic identity log(n^k) = k log(n). This demonstrates that log(n^k) scales linearly with k, indicating that the constant factor does not affect the asymptotic growth rate. The discussion also highlights the importance of understanding the base of the logarithm, which in this case is base 2. The Coefficient Rule for big O notation supports this conclusion, confirming that the presence of a constant multiplier does not change the overall classification. Thus, the proof hinges on recognizing the relationship between logarithmic expressions and their growth rates.
Gear2d
Messages
49
Reaction score
0
I was wondering how would I go about proving the Log of a Power Rule:

log(n^k) is O(log(n)) for any constant k > 0
 
Physics news on Phys.org
Think of a basic property of logarithms
 
You should show what you've tried, but basically..

log (n^k) = k log (n), and use w/e technique you want to show the constant up front does not matter.

OR are you asking how to prove the power rule for logs? I'll give a hint..

log (x) = y <=> 10^y = x

(assuming log has base 10 and <=> means if and only if).
 
mistermath said:
You should show what you've tried, but basically..

log (n^k) = k log (n), and use w/e technique you want to show the constant up front does not matter.

OR are you asking how to prove the power rule for logs? I'll give a hint..

log (x) = y <=> 10^y = x

(assuming log has base 10 and <=> means if and only if).

I see what you are saying when log (n^k) = k log (n) which is O(log (n)) based on Coefficient Rule ( http://www.augustana.ca/~hackw/csc210/exhibit/chap04/bigOhRules.html ). But, I am trying to prove the power rule for logs. Just don't know how to approach it or where to start off. And the log is base 2 and not 10 (sorry for got to mention that).
 

Thread 'Deductive proof in logic formal systems'

I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
View full post »

Similar threads

I Relation with Hessian and Log-likelihood
Replies
12
Views
2K
I Bayesian Information Criterion Formula Proof
Replies
4
Views
2K
MHB Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$
Replies
6
Views
2K
I Ways to put n balls in m boxes such that exactly k boxes are empty?
Replies
29
Views
3K
Derivative of Log Likelihood Function
Replies
5
Views
3K
I Variable transformation for a multivariate normal distribution
Replies
1
Views
2K
I Finding N / log(2) and M / log(3) very close together
Replies
9
Views
2K
MHB Log likelihood function and EM algorithm
Replies
16
Views
4K
Comp Sci Big O/Little O, Big Ω, little ω
Replies
1
Views
2K
Verify the convergence or divergence of a power series
Replies
17
Views
2K

Hot Threads

Recent Insights

Back
Top