Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big Oh Noatation Help

  1. Sep 20, 2008 #1
    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
  2. jcsd
  3. Sep 20, 2008 #2


    User Avatar
    Homework Helper

    Think of a basic property of logarithms
  4. Sep 20, 2008 #3
    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).
  5. Sep 20, 2008 #4
    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook