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

  • Thread starter Gear2d
  • Start date
In summary, the conversation discusses proving the Log of a Power Rule, where log (n^k) is O(log (n)) for any constant k > 0. The speaker suggests using a basic property of logarithms and showing that the constant does not affect the outcome. They also give a hint for proving the power rule for logs, which involves using the equation log (x) = y <=> 10^y = x (assuming log has base 10 and <=> means if and only if). The speaker mentions that they are unsure of how to approach or start the proof, and clarifies that the log is base 2.
  • #1
Gear2d
51
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
  • #2
Think of a basic property of logarithms
 
  • #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).
 
  • #4
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).
 

What is Big Oh Notation?

Big Oh Notation is a mathematical notation used in computer science to describe the complexity of algorithms. It represents the maximum amount of time or space required for an algorithm as the input size increases.

Why is Big Oh Notation important?

Big Oh Notation helps us analyze the performance of algorithms and make informed decisions about which ones to use in different situations. It also allows us to compare the efficiency of different algorithms.

How is Big Oh Notation calculated?

Big Oh Notation is calculated by looking at the number of operations an algorithm performs as the input size increases. The most dominant term is then used to represent the complexity, ignoring any coefficients or lower order terms.

What are the different types of Big Oh Notation?

The most common types of Big Oh Notation are O(1) (constant time), O(log n) (logarithmic time), O(n) (linear time), O(n^2) (quadratic time), and O(n!) (factorial time). There are also other variations such as O(n log n) and O(n^3).

How can Big Oh Notation be used in real-world applications?

Big Oh Notation can be used to analyze and improve the efficiency of algorithms in various applications, such as data sorting, searching, and optimization problems. It can also be used to predict the behavior of software systems as the amount of data they need to process increases.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
Replies
9
Views
1K
Replies
4
Views
696
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
567
Back
Top