Time complexity of an algorithm: Is it important to state the base of the logarithm?Complexity of finding the largest $m$ numbers in an array of size $n$The math behind converting from any base to any base without going through base 10?How many recursive calls are made by this gcd function?Time complexity of base conversionIs there any graph problem that, when restricted to trees, has $Omega(n^2)$ time complexity?Why is the log in the big-O of binary search not base 2?What is the deterministic time complexity of obtaining the set of distinct elements?What is the time complexity of MergeSort without its penultimate merge?Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithmWhat is the time complexity of the following algorithm on graphs
Alexandrov's generalization of Cauchy's rigidity theorem
Fill area of x^2+y^2>1 and x^2+y^2>4 using patterns and tikzpicture
Is a world with one country feeding everyone possible?
Could a rotating ring space station have a bolo-like extension?
How does the Earth's center produce heat?
Testing using real data of the customer
Why A=2 and B=1 in the call signs for Spirit and Opportunity?
Possibility of faking someone's public key
How do you earn the reader's trust?
Did Game of Thrones end the way that George RR Martin intended?
Prince of Darkness goes cryptic
Can a UK national work as a paid shop assistant in the USA?
Why Emacs (dired+) asks me twice to delete file?
Can diplomats be allowed on the flight deck of a commercial European airline?
Are cells guaranteed to get at least one mitochondrion when they divide?
Writing "hahaha" versus describing the laugh
Handling decimals in somewhat complex math
Why do the i8080 I/O instructions take a byte-sized operand to determine the port?
Comparison of bool data types in C++
If I arrive in the UK, and then head to mainland Europe, does my Schengen visa 90 day limit start when I arrived in the UK, or mainland Europe?
Negative impact of having the launch pad away from the Equator
Maximum interval between Alto & Tenor, & intervals when writing for SATB
Why is unzipped directory exactly 4.0K (much smaller than zipped file)?
The disk image is 497GB smaller than the target device
Time complexity of an algorithm: Is it important to state the base of the logarithm?
Complexity of finding the largest $m$ numbers in an array of size $n$The math behind converting from any base to any base without going through base 10?How many recursive calls are made by this gcd function?Time complexity of base conversionIs there any graph problem that, when restricted to trees, has $Omega(n^2)$ time complexity?Why is the log in the big-O of binary search not base 2?What is the deterministic time complexity of obtaining the set of distinct elements?What is the time complexity of MergeSort without its penultimate merge?Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithmWhat is the time complexity of the following algorithm on graphs
$begingroup$
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = Omega(logn)$, as opposed to $Omega(log_2n)$, or whatever the base might be?
algorithms time-complexity
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = Omega(logn)$, as opposed to $Omega(log_2n)$, or whatever the base might be?
algorithms time-complexity
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
3
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago
add a comment |
$begingroup$
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = Omega(logn)$, as opposed to $Omega(log_2n)$, or whatever the base might be?
algorithms time-complexity
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = Omega(logn)$, as opposed to $Omega(log_2n)$, or whatever the base might be?
algorithms time-complexity
algorithms time-complexity
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex5207Alex5207
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
Alex5207Alex5207
1323
asked 5 hours ago
Alex5207Alex5207
1323
1323
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alex5207 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
3
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago
add a comment |
3
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago
3
3
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $log_a n = Theta(log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
$endgroup$
add a comment |
$begingroup$
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $theta$ allows you to multiply by any constant.
If you take $O(2^log n)$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^0.3010)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
$endgroup$
add a comment |
$begingroup$
As $log_xy = frac1log_yx$ and $log_xy = fraclog_zylog_zx$, so $fraclog_anlog_bn = fraclog_nblog_na = log_ab$. As $log_ab$ is positive constant (for all $a,b > 1$), so $log_an = Theta(log_bn)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 4 hours ago
OmGOmG
1,500514
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Alex5207 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109607%2ftime-complexity-of-an-algorithm-is-it-important-to-state-the-base-of-the-logari%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $log_a n = Theta(log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
$endgroup$
add a comment |
$begingroup$
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $log_a n = Theta(log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
$endgroup$
add a comment |
$begingroup$
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $log_a n = Theta(log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
$endgroup$
Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $log_a n = Theta(log_b n)$ for all $a,b > 1$. So there is no need to specify the base of a logarithm when using asymptotic notation.
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
answered 5 hours ago
Yuval FilmusYuval Filmus
200k15190354
200k15190354
add a comment |
add a comment |
$begingroup$
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $theta$ allows you to multiply by any constant.
If you take $O(2^log n)$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^0.3010)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
$endgroup$
add a comment |
$begingroup$
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $theta$ allows you to multiply by any constant.
If you take $O(2^log n)$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^0.3010)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
$endgroup$
add a comment |
$begingroup$
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $theta$ allows you to multiply by any constant.
If you take $O(2^log n)$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^0.3010)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
$endgroup$
It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $theta$ allows you to multiply by any constant.
If you take $O(2^log n)$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^0.3010)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
edited 2 hours ago
Yuval Filmus
200k15190354
edited 2 hours ago
Yuval Filmus
200k15190354
edited 2 hours ago
Yuval Filmus
200k15190354
200k15190354
answered 3 hours ago
gnasher729gnasher729
12.9k1623
answered 3 hours ago
gnasher729gnasher729
12.9k1623
answered 3 hours ago
gnasher729gnasher729
12.9k1623
12.9k1623
add a comment |
add a comment |
$begingroup$
As $log_xy = frac1log_yx$ and $log_xy = fraclog_zylog_zx$, so $fraclog_anlog_bn = fraclog_nblog_na = log_ab$. As $log_ab$ is positive constant (for all $a,b > 1$), so $log_an = Theta(log_bn)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 4 hours ago
OmGOmG
1,500514
$endgroup$
add a comment |
$begingroup$
As $log_xy = frac1log_yx$ and $log_xy = fraclog_zylog_zx$, so $fraclog_anlog_bn = fraclog_nblog_na = log_ab$. As $log_ab$ is positive constant (for all $a,b > 1$), so $log_an = Theta(log_bn)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 4 hours ago
OmGOmG
1,500514
$endgroup$
add a comment |
$begingroup$
As $log_xy = frac1log_yx$ and $log_xy = fraclog_zylog_zx$, so $fraclog_anlog_bn = fraclog_nblog_na = log_ab$. As $log_ab$ is positive constant (for all $a,b > 1$), so $log_an = Theta(log_bn)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 4 hours ago
OmGOmG
1,500514
$endgroup$
As $log_xy = frac1log_yx$ and $log_xy = fraclog_zylog_zx$, so $fraclog_anlog_bn = fraclog_nblog_na = log_ab$. As $log_ab$ is positive constant (for all $a,b > 1$), so $log_an = Theta(log_bn)$.
edited 2 hours ago
Yuval Filmus
200k15190354
answered 4 hours ago
OmGOmG
1,500514
edited 2 hours ago
Yuval Filmus
200k15190354
edited 2 hours ago
Yuval Filmus
200k15190354
edited 2 hours ago
Yuval Filmus
200k15190354
200k15190354
answered 4 hours ago
OmGOmG
1,500514
answered 4 hours ago
OmGOmG
1,500514
answered 4 hours ago
OmGOmG
1,500514
1,500514
add a comment |
add a comment |
Alex5207 is a new contributor. Be nice, and check out our Code of Conduct.
Alex5207 is a new contributor. Be nice, and check out our Code of Conduct.
Alex5207 is a new contributor. Be nice, and check out our Code of Conduct.
Alex5207 is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109607%2ftime-complexity-of-an-algorithm-is-it-important-to-state-the-base-of-the-logari%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
Yes, you are correct.
$endgroup$
– Juho
5 hours ago