Otdfbt

Is a diamond sword feasible?

Control variables and other independent variables

Is it a bad idea to replace pull-up resistors with hard pull-ups?

How could we transfer large amounts of energy sourced in space to Earth?

Was there ever any real use for a 6800-based Apple I?

Why does the Earth follow an elliptical trajectory rather than a parabolic one?

Will change of address affect direct deposit?

"Right on the tip of my tongue" meaning?

How to make the table in the figure in LaTeX?

Thesis' "Future Work" section – is it acceptable to omit personal involvement in a mentioned project?

Should these notes be played as a chord or one after another?

Ex-manager wants to stay in touch, I don't want to

Exception propagation: When to catch exceptions?

How are one-time password generators like Google Authenticator different from having two passwords?

Was this a power play by Daenerys?

Is Simic Ascendancy triggered by Awakening of Vitu-Ghazi?

How to make a language evolve quickly?

How do I compare the result of "1d20+x, with advantage" to "1d20+y, without advantage", assuming x < y?

Is "now" UTC time in Solidity?

"Fīliolō me auctum scito, salva Terentia"; what is "me" role in this phrase?

Can 'sudo apt-get remove [write]' destroy my Ubuntu?

How to pronounce "r" after a "g"?

Are there variations of the regular runtimes of the Big-O-Notation?

Why do unstable nuclei form?

Is it true that $3^n = 2^O(n)$?

Big O Notation ClarificationHow to show that for all k, $k! ge (k/2)^k/2$Is it true that $ f(n) = O(g(n))$ implies $g(n) = O(f(n))$Does any quadratic function in the form $an^2 + bn + c$ equal $Theta(n^2)$ in asymptotic notation?Big O notaion O(n) and logaritmsHelp Calculating Computer Time used by AlgorithmsBig - O: Why does $7x^2$ differ from $3x$?Big Oh Analysis of FunctionsUnderstanding Asymptotic NotationBig O notation True or False

3

$begingroup$

I know that the two main rules are dropping low order terms and dropping constant factors.

For example:

$50n = O(n)$

$5n^2 + 3n + 45 = O(n^2)$

But in a textbook I found the question:

Is it true that $3^n = 2^O(n)$?

The answer is true but I do not understand why it is not $3^O(n)$. I know you cannot just drop the base completely but why is $3$ changed to $2$?

combinatorics asymptotics

share|cite|improve this question

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

$endgroup$

add a comment | 

3

$begingroup$

I know that the two main rules are dropping low order terms and dropping constant factors.

For example:

$50n = O(n)$

$5n^2 + 3n + 45 = O(n^2)$

But in a textbook I found the question:

Is it true that $3^n = 2^O(n)$?

The answer is true but I do not understand why it is not $3^O(n)$. I know you cannot just drop the base completely but why is $3$ changed to $2$?

combinatorics asymptotics

share|cite|improve this question

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

$endgroup$

add a comment | 

$begingroup$

I know that the two main rules are dropping low order terms and dropping constant factors.

For example:

$50n = O(n)$

$5n^2 + 3n + 45 = O(n^2)$

But in a textbook I found the question:

Is it true that $3^n = 2^O(n)$?

The answer is true but I do not understand why it is not $3^O(n)$. I know you cannot just drop the base completely but why is $3$ changed to $2$?

combinatorics asymptotics

share|cite|improve this question

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

$endgroup$

share|cite|improve this question

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

share|cite|improve this question

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

edited May 1 at 14:04

YuiTo Cheng

3,24361145

edited May 1 at 14:04

YuiTo Cheng

3,24361145

asked May 1 at 8:24

JovialnessJovialness

184

asked May 1 at 8:24

JovialnessJovialness

184

2 Answers
2

active

oldest

votes

5

$begingroup$

Let's try to solve $3^n = 2^m$ for $m$.

First, use a log on both sides:
$$n log(3) = m log(2).$$

Now, solve for $m$:
$$m = fraclog(3)log(2) n.$$

Obviously, we now have $m = O(n)$, they only differ by a constant. Therefore, we can say
$$3^n = 2^O(n).$$

So yes, in some sense you can drop the base, we always have
$$a^n = b^O(n)$$
as long as $a,b > 1$.

Note that it wasn't claimed that
$$3^n = O(2^n),$$
as this would be wrong.

share|cite|improve this answer

answered May 1 at 8:33

DirkDirk

5,206219

$endgroup$

add a comment | 

5

$begingroup$

$largedisplaystyle 3^n = 2^n cdot log_23$

Notice that $log_23$ is a constant, so it can be written as $2^O(n)$.

Yes, it could be written as $3^textO(n)$, but the question was just asking if it's true.

share|cite|improve this answer

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3209279%2fis-it-true-that-3n-2on%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

Let's try to solve $3^n = 2^m$ for $m$.

First, use a log on both sides:
$$n log(3) = m log(2).$$

Now, solve for $m$:
$$m = fraclog(3)log(2) n.$$

Obviously, we now have $m = O(n)$, they only differ by a constant. Therefore, we can say
$$3^n = 2^O(n).$$

So yes, in some sense you can drop the base, we always have
$$a^n = b^O(n)$$
as long as $a,b > 1$.

Note that it wasn't claimed that
$$3^n = O(2^n),$$
as this would be wrong.

share|cite|improve this answer

answered May 1 at 8:33

DirkDirk

5,206219

$endgroup$

add a comment | 

5

$begingroup$

Let's try to solve $3^n = 2^m$ for $m$.

First, use a log on both sides:
$$n log(3) = m log(2).$$

Now, solve for $m$:
$$m = fraclog(3)log(2) n.$$

Obviously, we now have $m = O(n)$, they only differ by a constant. Therefore, we can say
$$3^n = 2^O(n).$$

So yes, in some sense you can drop the base, we always have
$$a^n = b^O(n)$$
as long as $a,b > 1$.

Note that it wasn't claimed that
$$3^n = O(2^n),$$
as this would be wrong.

share|cite|improve this answer

answered May 1 at 8:33

DirkDirk

5,206219

$endgroup$

add a comment | 

$begingroup$

Let's try to solve $3^n = 2^m$ for $m$.

First, use a log on both sides:
$$n log(3) = m log(2).$$

Now, solve for $m$:
$$m = fraclog(3)log(2) n.$$

Obviously, we now have $m = O(n)$, they only differ by a constant. Therefore, we can say
$$3^n = 2^O(n).$$

So yes, in some sense you can drop the base, we always have
$$a^n = b^O(n)$$
as long as $a,b > 1$.

Note that it wasn't claimed that
$$3^n = O(2^n),$$
as this would be wrong.

share|cite|improve this answer

answered May 1 at 8:33

DirkDirk

5,206219

$endgroup$

share|cite|improve this answer

answered May 1 at 8:33

DirkDirk

5,206219

answered May 1 at 8:33

DirkDirk

5,206219

answered May 1 at 8:33

DirkDirk

5,206219

5

$begingroup$

$largedisplaystyle 3^n = 2^n cdot log_23$

Notice that $log_23$ is a constant, so it can be written as $2^O(n)$.

Yes, it could be written as $3^textO(n)$, but the question was just asking if it's true.

share|cite|improve this answer

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

$endgroup$

add a comment | 

5

$begingroup$

$largedisplaystyle 3^n = 2^n cdot log_23$

Notice that $log_23$ is a constant, so it can be written as $2^O(n)$.

Yes, it could be written as $3^textO(n)$, but the question was just asking if it's true.

share|cite|improve this answer

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

$endgroup$

add a comment | 

$begingroup$

$largedisplaystyle 3^n = 2^n cdot log_23$

Notice that $log_23$ is a constant, so it can be written as $2^O(n)$.

Yes, it could be written as $3^textO(n)$, but the question was just asking if it's true.

share|cite|improve this answer

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

$endgroup$

share|cite|improve this answer

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535

answered May 1 at 8:35

Saketh MalyalaSaketh Malyala

8,4331535