Dtjytyk

Why is "Consequences inflicted." not a sentence?

Storing hydrofluoric acid before the invention of plastics

Were Kohanim forbidden from serving in King David's army?

"Seemed to had" is it correct?

Antler Helmet: Can it work?

What do you call a phrase that's not an idiom yet?

What's the purpose of writing one's academic bio in 3rd person?

Can inflation occur in a positive-sum game currency system such as the Stack Exchange reputation system?

What are the motives behind Cersei's orders given to Bronn?

What does '1 unit of lemon juice' mean in a grandma's drink recipe?

Output the ŋarâþ crîþ alphabet song without using (m)any letters

What is this single-engine low-wing propeller plane?

Why was the term "discrete" used in discrete logarithm?

Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?

What's the difference between `auto x = vector<int>()` and `vector<int> x`?

Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?

If 'B is more likely given A', then 'A is more likely given B'

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

What do you call a plan that's an alternative plan in case your initial plan fails?

What would be the ideal power source for a cybernetic eye?

Does surprise arrest existing movement?

Determinant is linear as a function of each of the rows of the matrix.

Models of set theory where not every set can be linearly ordered

Proof involving the spectral radius and the Jordan canonical form

Prove whether $f(n)$ is $O$, $o$, $Omega$, $omega$ or $Theta$ of $g(n)$. $f(n) = n + (log n)^{2}$, $g(n) = n + log(n^{2})$.

0

$begingroup$

$f(n) = n + (log n)^{2} , g(n) = n + log(n^{2} ).$

Now so far I've done $g(n) = n+ 2log(n)$

and then I think since its the same change to both, I can remove $n$.

leaving me with $f(n) = (log n)^{2}$ and $g(n) = 2log(n)$ now if I do $f(n)/g(n)$ I get

$((log n)^{2}) / (2log n)$

and since the numerator is growing exponentially and the bottom is growing linearly? As we approach positive infinity the function approaches positive infinity. Thus $f(n)$ is $omega$ of $g(n)$?

I don't know if this proof is done right, if its what is a better alternative? I am still new to this and learning!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Don't remove $n$. Do $lim_{ntoinfty}frac{n+(log(n))^2}{n+2log(n)}=lim_{ntoinfty}frac{1+(log(n))^2/n}{1+2(log(n))/n}=1$.
  $endgroup$
  – user647486
  Mar 23 at 23:43
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  what should I do instead then?
  $endgroup$
  – Brownie
  Mar 23 at 23:44
  

  
  
  
  

add a comment | 

0

$begingroup$

$f(n) = n + (log n)^{2} , g(n) = n + log(n^{2} ).$

Now so far I've done $g(n) = n+ 2log(n)$

and then I think since its the same change to both, I can remove $n$.

leaving me with $f(n) = (log n)^{2}$ and $g(n) = 2log(n)$ now if I do $f(n)/g(n)$ I get

$((log n)^{2}) / (2log n)$

and since the numerator is growing exponentially and the bottom is growing linearly? As we approach positive infinity the function approaches positive infinity. Thus $f(n)$ is $omega$ of $g(n)$?

I don't know if this proof is done right, if its what is a better alternative? I am still new to this and learning!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Don't remove $n$. Do $lim_{ntoinfty}frac{n+(log(n))^2}{n+2log(n)}=lim_{ntoinfty}frac{1+(log(n))^2/n}{1+2(log(n))/n}=1$.
  $endgroup$
  – user647486
  Mar 23 at 23:43
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  what should I do instead then?
  $endgroup$
  – Brownie
  Mar 23 at 23:44
  

  
  
  
  

add a comment | 

$begingroup$

$f(n) = n + (log n)^{2} , g(n) = n + log(n^{2} ).$

Now so far I've done $g(n) = n+ 2log(n)$

and then I think since its the same change to both, I can remove $n$.

leaving me with $f(n) = (log n)^{2}$ and $g(n) = 2log(n)$ now if I do $f(n)/g(n)$ I get

$((log n)^{2}) / (2log n)$

and since the numerator is growing exponentially and the bottom is growing linearly? As we approach positive infinity the function approaches positive infinity. Thus $f(n)$ is $omega$ of $g(n)$?

I don't know if this proof is done right, if its what is a better alternative? I am still new to this and learning!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

$endgroup$

share|cite|improve this question

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

share|cite|improve this question

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

edited Mar 24 at 3:00

Rócherz

3,0263823

edited Mar 24 at 3:00

Rócherz

3,0263823

asked Mar 23 at 23:32

BrownieBrownie

3327

asked Mar 23 at 23:32

BrownieBrownie

3327

2 Answers
2

active

oldest

votes

1

$begingroup$

$frac {f(n)} {g(n)}=frac {n+(log, n)^{2}}{ n+2log, n}=frac {1+(log, n)^{2}/n} { 1+2(log, n)/n} to 1$

share|cite|improve this answer

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Did you just divide by n on the top and bottom?
  $endgroup$
  – Brownie
  Mar 23 at 23:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Yes, that is what I did. To see that the second terms in the numerator and denominator both tend to $0$ you can apply L'Hopital's rule.
  $endgroup$
  – Kavi Rama Murthy
  Mar 23 at 23:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry I know this is a bit later, I still dont understand how the f(n)/g(n) tends to 1. The numerator and denominator tend towards 0 as it is, and even after applying l'hopital's rule. I am confused
  $endgroup$
  – Brownie
  Mar 25 at 20:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Use L'Hopital's Rule to show that $frac {log, n} n to 0$ and $frac {(log, n)^{2}} n to 0$.
  $endgroup$
  – Kavi Rama Murthy
  Mar 25 at 23:04
  

  
  
  
  

add a comment | 

0

$begingroup$

You're pretty much done with $O$ by doing the $g(n) = n+ 2log(n)$ transformation, since
$$f(n) = n + (log n)^{2} \
g(n) = n + 2 log(n)$$
Assuming that $log$ means $ln$:
$$forall n ge 8 quad f(n) > g(n)$$
Since $ln(8) > 2$, and $ln$ is monotone increasing.

This means that $g(n) = O(f(n))$.

share|cite|improve this answer

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  log is base 2 in this case
  $endgroup$
  – Brownie
  Mar 23 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Which is less information than $fsim g$.
  $endgroup$
  – user647486
  Mar 23 at 23:59
  

  
  
  
  

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%2f3159926%2fprove-whether-fn-is-o-o-omega-omega-or-theta-of-gn-fn%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

$frac {f(n)} {g(n)}=frac {n+(log, n)^{2}}{ n+2log, n}=frac {1+(log, n)^{2}/n} { 1+2(log, n)/n} to 1$

share|cite|improve this answer

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Did you just divide by n on the top and bottom?
  $endgroup$
  – Brownie
  Mar 23 at 23:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Yes, that is what I did. To see that the second terms in the numerator and denominator both tend to $0$ you can apply L'Hopital's rule.
  $endgroup$
  – Kavi Rama Murthy
  Mar 23 at 23:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry I know this is a bit later, I still dont understand how the f(n)/g(n) tends to 1. The numerator and denominator tend towards 0 as it is, and even after applying l'hopital's rule. I am confused
  $endgroup$
  – Brownie
  Mar 25 at 20:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Use L'Hopital's Rule to show that $frac {log, n} n to 0$ and $frac {(log, n)^{2}} n to 0$.
  $endgroup$
  – Kavi Rama Murthy
  Mar 25 at 23:04
  

  
  
  
  

add a comment | 

1

$begingroup$

$frac {f(n)} {g(n)}=frac {n+(log, n)^{2}}{ n+2log, n}=frac {1+(log, n)^{2}/n} { 1+2(log, n)/n} to 1$

share|cite|improve this answer

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Did you just divide by n on the top and bottom?
  $endgroup$
  – Brownie
  Mar 23 at 23:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Yes, that is what I did. To see that the second terms in the numerator and denominator both tend to $0$ you can apply L'Hopital's rule.
  $endgroup$
  – Kavi Rama Murthy
  Mar 23 at 23:51
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry I know this is a bit later, I still dont understand how the f(n)/g(n) tends to 1. The numerator and denominator tend towards 0 as it is, and even after applying l'hopital's rule. I am confused
  $endgroup$
  – Brownie
  Mar 25 at 20:10
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Brownie Use L'Hopital's Rule to show that $frac {log, n} n to 0$ and $frac {(log, n)^{2}} n to 0$.
  $endgroup$
  – Kavi Rama Murthy
  Mar 25 at 23:04
  

  
  
  
  

add a comment | 

$begingroup$

$frac {f(n)} {g(n)}=frac {n+(log, n)^{2}}{ n+2log, n}=frac {1+(log, n)^{2}/n} { 1+2(log, n)/n} to 1$

share|cite|improve this answer

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

$endgroup$

share|cite|improve this answer

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

answered Mar 23 at 23:47

Kavi Rama MurthyKavi Rama Murthy

74.9k53270

0

$begingroup$

You're pretty much done with $O$ by doing the $g(n) = n+ 2log(n)$ transformation, since
$$f(n) = n + (log n)^{2} \
g(n) = n + 2 log(n)$$
Assuming that $log$ means $ln$:
$$forall n ge 8 quad f(n) > g(n)$$
Since $ln(8) > 2$, and $ln$ is monotone increasing.

This means that $g(n) = O(f(n))$.

share|cite|improve this answer

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  log is base 2 in this case
  $endgroup$
  – Brownie
  Mar 23 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Which is less information than $fsim g$.
  $endgroup$
  – user647486
  Mar 23 at 23:59
  

  
  
  
  

add a comment | 

0

$begingroup$

You're pretty much done with $O$ by doing the $g(n) = n+ 2log(n)$ transformation, since
$$f(n) = n + (log n)^{2} \
g(n) = n + 2 log(n)$$
Assuming that $log$ means $ln$:
$$forall n ge 8 quad f(n) > g(n)$$
Since $ln(8) > 2$, and $ln$ is monotone increasing.

This means that $g(n) = O(f(n))$.

share|cite|improve this answer

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  log is base 2 in this case
  $endgroup$
  – Brownie
  Mar 23 at 23:55
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Which is less information than $fsim g$.
  $endgroup$
  – user647486
  Mar 23 at 23:59
  

  
  
  
  

add a comment | 

$begingroup$

You're pretty much done with $O$ by doing the $g(n) = n+ 2log(n)$ transformation, since
$$f(n) = n + (log n)^{2} \
g(n) = n + 2 log(n)$$
Assuming that $log$ means $ln$:
$$forall n ge 8 quad f(n) > g(n)$$
Since $ln(8) > 2$, and $ln$ is monotone increasing.

This means that $g(n) = O(f(n))$.

share|cite|improve this answer

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

$endgroup$

share|cite|improve this answer

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

edited Mar 24 at 3:01

Rócherz

3,0263823

edited Mar 24 at 3:01

Rócherz

3,0263823

answered Mar 23 at 23:54

Daniel PDaniel P

69714

answered Mar 23 at 23:54

Daniel PDaniel P

69714