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

  • Context: Graduate 
  • Thread starter Thread starter Gear2d
  • Start date Start date
Click For Summary

Discussion Overview

The discussion centers around proving the Log of a Power Rule, specifically that log(n^k) is O(log(n)) for any constant k > 0. The scope includes theoretical aspects of logarithmic properties and their implications in algorithm analysis.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant inquires about the approach to prove that log(n^k) is O(log(n)).
  • Another participant suggests considering basic properties of logarithms as a starting point.
  • It is noted that log(n^k) can be expressed as k log(n), and participants discuss using this expression to demonstrate that the constant factor does not affect the big O notation.
  • There is a mention of the Coefficient Rule in big O notation as a potential support for the claim.
  • A participant expresses confusion about whether the discussion is about proving the power rule for logs or the big O relationship, indicating a need for clarification on the topic.
  • It is clarified that the logarithm in question is base 2, not base 10, which may influence the discussion.

Areas of Agreement / Disagreement

Participants appear to have differing interpretations of the initial question, with some focusing on the big O relationship and others on the power rule itself. No consensus is reached on the specific approach to take for the proof.

Contextual Notes

There is an indication that assumptions about the logarithmic base and the nature of the proof may not be fully articulated, which could affect the clarity of the discussion.

Who May Find This Useful

This discussion may be useful for students or individuals interested in algorithm analysis, logarithmic properties, and mathematical proofs related to big O notation.

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).
 

Similar threads

Undergrad Finding N / log(2) and M / log(3) very close together
  • · Replies 9 ·
Replies
9
Views
2K
High School Log(x), an easy and useful way to calculate it
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Relation with Hessian and Log-likelihood
  • · Replies 12 ·
Replies
12
Views
2K
Undergrad Bayesian Information Criterion Formula Proof
  • · Replies 4 ·
Replies
4
Views
2K
MHB Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$
  • · Replies 6 ·
Replies
6
Views
2K
High School I do not understand Log tables
  • · Replies 15 ·
Replies
15
Views
4K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Graduate Derivative of Log Likelihood Function
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Variable transformation for a multivariate normal distribution
  • · Replies 1 ·
Replies
1
Views
2K
MHB Log likelihood function and EM algorithm
  • · Replies 16 ·
Replies
16
Views
4K