f (n) = log10 n ∈O(log n)

so far according to me c = 1 and k = 1, which proves that the above notation is correct, but I am not sure if it is that simple and I don't know how to break it down into steps to prove it. Does someone know how to break it down into steps.

CodePudding user response：

It's not sufficient to give a pair of constants for which you think the definition of Big O is true unfortunately. :) You have to actually prove that those constants work.

Since you're asking for steps to prove this (and not for someone to prove it for you), I'll do my best to give you some steps to start with.

Firstly, for this problem, I suggest you review three pieces of information that will be helpful for you:

1. The definition of Big 0. f(n) ∈ O(g(n)) if and only if f(n) ≤ c∙g(n) for all n ≥ n₀ and some constant c > 0. If this definition doesn't ring a bell, then you will need to take a few steps back and review this in more depth.

2. Since the world of computer science generally defaults to using base 2, when we say log n, we really mean log₂ n. (I'm assuming you're asking this for a computer science-related reason, but if not, you can ignore this piece and still solve your problem.)

3. Logarithm rules. Recall that log_a b = log_c b / log_c a

Now, see if you can use these three pieces of information to prove that f(n) = log₁₀ n ∈ O(log n).