I'm trying to understand the correct answer to the following question:
The answer was that all were true because lgn can be said to be theta of log8n, which includes all three of the choices.
This is confusing to me because for any positive value of n, logn is going to be larger than log8n, correct?. To say that logn is tightly bound by log8n would mean that logn is both Big O of log8n and Big Omega of log8n. Or in plain English, logn is no greater than k1 x log8n and no less than k2 x log8n.
My answer was that logn was Big Omega of log8n because it should never take less time. Why is this wrong?
Assuming that lg denotes natural logarithm, one has that log_8(n)=lg(n)/lg(8) thus those two functions differ only via a multiplicative factor.
Now, let's inspect for example the Big O case from this table, where f is lg and g stands for log_8. If we set k=lg(8), then the condition in the third column is satisfied automatically. In other words, the condition "|f| is bounded above by g (up to constant factor)" is satisfied, since, in loose terms, those two functions are in fact the same up to constant (multiplicative) factor.
The same reasoning applies to Big Omega and therefore one obtains Big Theta as well (which you get directly with k1=k2=lg(8) in its definition)
