Complexity analysis of logarithms

I have two functions, f(n)=log(base 2)n and g(n)=log(base 10)n. I am trying to decide whether f(n) is O(g(n)), or Ω(g(n)) or Θ(g(n)). I thinks i should take the limit f(n)/g(n) as n goes to infinity, and i think that limit is constant so f(n) must be Θ(g(n)). Am i right? Thanks in advance

-

The quantity $f(n)/g(n)$ is constant, that is, independent of $n$. – Gerry Myerson Feb 26 at 11:58

1 Answer

You can rely on a useful and often-forgotten result, that $(\log_a b)(\log_b c) = \log_a c$, so in your problem we'll have $$(\log_2 10)g(n) = (\log_2 10)(\log_{10} n) = \log_2 n = f(n)$$ so $f(n)$ is just a constant multiple ($\log_2 10\approx 3.32$) of $g(n)$ and hence $f(n)=\Theta(g(n))$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9111267328262329, "perplexity_flag": "middle"}