Fdtxjr

How to notate time signature switching consistently every measure

Slides for 30 min~1 hr Skype tenure track application interview

Falsification in Math vs Science

What is the motivation for a law requiring 2 parties to consent for recording a conversation

If a sorcerer casts the Banishment spell on a PC while in Avernus, does the PC return to their home plane?

Relationship between Gromov-Witten and Taubes' Gromov invariant

Why doesn't UInt have a toDouble()?

What's the name of these plastic connectors

How to translate "being like"?

writing variables above the numbers in tikz picture

What do hard-Brexiteers want with respect to the Irish border?

Dropping list elements from nested list after evaluation

Likelihood that a superbug or lethal virus could come from a landfill

What is preventing me from simply constructing a hash that's lower than the current target?

What to do when moving next to a bird sanctuary with a loosely-domesticated cat?

Output the Arecibo Message

What is the meaning of Triage in Cybersec world?

Is it correct to say the Neural Networks are an alternative way of performing Maximum Likelihood Estimation? if not, why?

Why “相同意思的词” is called “同义词” instead of "同意词"？

Why isn't the circumferential light around the M87 black hole's event horizon symmetric?

Why couldn't they take pictures of a closer black hole?

Inverse Relationship Between Precision and Recall

Is bread bad for ducks?

How can I add encounters in the Lost Mine of Phandelver campaign without giving PCs too much XP?

Is this solution correct? Prove whether $f(n)$ is $O$, $o$, $Omega$, $omega$ or $Theta$ of $g(n)$

0

$begingroup$

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

log is assumed to be base 2

So I differentiated each of the functions

$f(n)' = 1 + 2(log n)$

$g(n)' = 1 + (2/nln(2))$

and then finding the limit of $f(n)' / g(n)'$ as $n$ approaches infinity. Which the denominator approaches 1, while the numerator approaches infinity. Thus, $f(n) = omega g(n)$?

Is this correct? I'm pretty new so if you could guide me I'd appreciate it!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You should check your derivatives.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 5:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I checked them and got the same answer, I might be doing it wrong though. So for f(n) both 1 and $(logn)^2$ followed the power rule, so that one seems correct. For g(n) I changed $log(n^2)$ into $2log(n)$ before differentiating. The n in g(n) becomes 1, and the log(n) becomes $1/nln(2)$ and multiplied by 2 at the end since that is a constant. I don't see my mistake, I am pretty new though so I have probably made an error. Could you point it out?
  $endgroup$
  – Brownie
  Mar 24 at 5:52
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The derivative of $(log n)^2$ is $2log n$ times the derivative of $log n$.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 6:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh can you not use the power rule on (log n)^2? I will rework and edit!
  $endgroup$
  – Brownie
  Mar 24 at 6:07
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The rule used to differentiate $(log n)^2$ is the chain rule. Both functions are $Theta(n)$. As you proceed in your study of asymptotics, you'll learn that $n$ dominates the logarithmic terms.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 6:30
  

  
  
  
  

 | 
show 1 more comment

0

$begingroup$

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

log is assumed to be base 2

So I differentiated each of the functions

$f(n)' = 1 + 2(log n)$

$g(n)' = 1 + (2/nln(2))$

and then finding the limit of $f(n)' / g(n)'$ as $n$ approaches infinity. Which the denominator approaches 1, while the numerator approaches infinity. Thus, $f(n) = omega g(n)$?

Is this correct? I'm pretty new so if you could guide me I'd appreciate it!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  You should check your derivatives.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 5:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I checked them and got the same answer, I might be doing it wrong though. So for f(n) both 1 and $(logn)^2$ followed the power rule, so that one seems correct. For g(n) I changed $log(n^2)$ into $2log(n)$ before differentiating. The n in g(n) becomes 1, and the log(n) becomes $1/nln(2)$ and multiplied by 2 at the end since that is a constant. I don't see my mistake, I am pretty new though so I have probably made an error. Could you point it out?
  $endgroup$
  – Brownie
  Mar 24 at 5:52
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The derivative of $(log n)^2$ is $2log n$ times the derivative of $log n$.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 6:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Oh can you not use the power rule on (log n)^2? I will rework and edit!
  $endgroup$
  – Brownie
  Mar 24 at 6:07
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The rule used to differentiate $(log n)^2$ is the chain rule. Both functions are $Theta(n)$. As you proceed in your study of asymptotics, you'll learn that $n$ dominates the logarithmic terms.
  $endgroup$
  – Fabio Somenzi
  Mar 24 at 6:30
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

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

log is assumed to be base 2

So I differentiated each of the functions

$f(n)' = 1 + 2(log n)$

$g(n)' = 1 + (2/nln(2))$

and then finding the limit of $f(n)' / g(n)'$ as $n$ approaches infinity. Which the denominator approaches 1, while the numerator approaches infinity. Thus, $f(n) = omega g(n)$?

Is this correct? I'm pretty new so if you could guide me I'd appreciate it!

discrete-mathematics asymptotics computer-science

share|cite|improve this question

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

$endgroup$

share|cite|improve this question

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

share|cite|improve this question

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

edited Mar 24 at 5:36

Fabio Somenzi

6,52821321

asked Mar 24 at 5:04

BrownieBrownie

3327

asked Mar 24 at 5:04

BrownieBrownie

3327