How do you compare the big-Oh growth rate of a logarithmic function to a non-logarithmic function?

[vaderboi]

Note: Please do not flag my quoted description below! It appears in two posts I made in the last couple days because I want to make sure someone reading any of my questions about big-Oh notation can understand the background context me having to write it out every single time I post. It's just a way to save myself some redundancy and time.

I am majoring in Computer Science and am taking a Data Structures class. We are studying big-Oh notation which allows you to compare how one function grows compared to another. To find whether a function is big-Oh of another we would say that:

For functions f(x) and g(x), we will say that "f(x) is O(g(x))” [pronounced "(x) is big-oh of g(x)"] if there are positive constants C and k such that
|f(x)|≤C|g(x)| for all x>k.

(This definition found at https://www.cs.sfu.ca/~ggbaker/zju/math/growth.html)

I understand that for f(x) to be big-Oh of g(x) there must exist at least one corresponding C and k such that g(x) will grow either equally or faster than f(x) forever more when x becomes greater than k.

So logarithms are really confusing to me and I am having a difficult time understanding them. In a homework assignment I am doing, I am supposed to assess various functions and determine whether they are an element of the class of all functions represented by O(x). One of the questions asks me to assess whether 5 * (log x) is an element of O(x).

Normally to figure the growth relationship out I solve for the constant and see if the constant stays a constant. If it becomes more than or equal to a function then I know that there is no valid constant that exists.

This is what I have done so far:

|5 log x| <= C * |x|
5 log x/ x <= C
log x⁵/ x <= C

But then I get stuck because I have no idea how to reduce the quotient so that it reveals whether it is a constant or a function. I understand that log x essentially represents d^y = x with d representing some base. But I don't know how to have a logarithmic function and a non-logarithmic function interact with each other if that makes sense.

Can anyone provide any illumination?

 

[Steven G]

5 log x/ x <= C is the same as log x/ x <= C /5 = another constant, say C'
log x/ x <= C'
So you want to prove that there exists a C' such that logx/x <=C'
Hint: Have you taken Calculus 1? Did you learn how to find the maximum value of a function?

For the record you could work with log x⁵/ x <= C but it will be slightly harder than working with logx/x

 

[vaderboi]

I should have written down that I was trying to figure out what value of C exists such that log x / x <= C since I know that log x < 5 log x . Since it is less, it would still allow the inequality 5 log x <= C * x for some C and k to be true.

So yes, I do want to find what value of C makes it more than equal or equal to log x / x.

No, I never took Calculus. How could knowing about maximum values of functions help me? I can take a look at that if it will help me solve the problem.

 

[Steven G]

I should have written down that I was trying to figure out what value of C exists such that log x / x <= C since I know that log x < 5 log x . Since it is less, it would still allow the inequality 5 log x <= C * x for some C and k to be true.

So yes, I do want to find what value of C makes it more than equal or equal to log x / x.

No, I never took Calculus. How could knowing about maximum values of functions help me? I can take a look at that if it will help me solve the problem.

Suppose the maximum value of logx/x is 15 at x=7. Will this help you get a C?

 

[vaderboi]

Not in this case, I don't think. I can choose what C and k are but the C and k I choose has to work for ALL x > k