MHB What is the dominant term of a function and its complexity?

[evinda]

Hey again! (Smile)

I want to find the complexity of $g(n)=10 \cdot \log (n^{30}+30)+2 $.

We will find that $g(n)=\Theta(\log n)$, right? (Thinking)

What can I say at the beginning? Which is the dominant term of the function? (Thinking)

 

[I like Serena]

Hey again! (Smile)

I want to find the complexity of $g(n)=10 \cdot \log (n^{30}+30)+2 $.

We will find that $g(n)=\Theta(\log n)$, right? (Thinking)

What can I say at the beginning? Which is the dominant term of the function? (Thinking)

Hi again! (Happy)

Since $30$ can be neglected with respect to $n^{30}$, I'd say that the dominant term is $10\cdot \log(n^{30})$.

 

[evinda]

Hi again! (Happy)

Since $30$ can be neglected with respect to $n^{30}$, I'd say that the dominant term is $10\cdot \log(n^{30})$.

A ok! (Nod) This is equal to $10 \cdot 30 \cdot \log n$, right?

 

[I like Serena]

A ok! (Nod) This is equal to $10 \cdot 30 \cdot \log n$, right?

Right! (Mmm)

 

[evinda]

Right! (Mmm)

So, could we say that the dominant term is equal to $\log n$ ? (Thinking)

 

[I like Serena]

So, could we say that the dominant term is equal to $\log n$ ? (Thinking)

I guess it depends a bit how the phrase "dominant term" is defined exactly. (Wondering)

Taken literally, it's the term that grows more rapidly than any other in the expression.
As such your dominant term would be $10\cdot \log(n^{30}+30)$. (Nerd)

 

[evinda]

I guess it depends a bit how the phrase "dominant term" is defined exactly. (Wondering)

Taken literally, it's the term that grows more rapidly than any other in the expression.
As such your dominant term would be $10\cdot \log(n^{30}+30)$. (Nerd)

So, in this case $g(n)$ isn't equal to $\Theta( \text{ dominant term})$, right? (Thinking)

What else could I write at the beginning, to say that $g(n)=\Theta(\log n)$ ?

 

[I like Serena]

So, in this case $g(n)$ isn't equal to $\Theta( \text{ dominant term})$, right? (Thinking)

But it is equal to that! (Wait)

It's just that $\Theta(10\cdot \log(n^{30}+30)) = \Theta(\log(n))$. (Nod)

What else could I write at the beginning, to say that $g(n)=\Theta(\log n)$ ?

Well, you could say that the dominant term is $10\cdot \log(n^{30}+30)$, so $g(n)$ is asymptotically equal to $10\cdot \log(n^{30}+30)$.

And since the dominant term of $n^{30}+30$ is $n^{30}$, it follows that $g(n)$ is asymptotically equal to $10\cdot \log(n^{30})$, which is the same as $300\log(n)$.

In turn, that is asymptotically equal to $\log(n)$.

So:
$$g(n) = \Theta(10\cdot \log(n^{30}+30)) = \Theta(10\cdot \log(n^{30}))
=\Theta(300 \log(n))=\Theta(\log(n))$$
(Mmm)

 

[evinda]

But it is equal to that! (Wait)

It's just that $\Theta(10\cdot \log(n^{30}+30)) = \Theta(\log(n))$. (Nod)

Well, you could say that the dominant term is $10\cdot \log(n^{30}+30)$, so $g(n)$ is asymptotically equal to $10\cdot \log(n^{30}+30)$.

And since the dominant term of $n^{30}+30$ is $n^{30}$, it follows that $g(n)$ is asymptotically equal to $10\cdot \log(n^{30})$, which is the same as $300\log(n)$.

In turn, that is asymptotically equal to $\log(n)$.

So:
$$g(n) = \Theta(10\cdot \log(n^{30}+30)) = \Theta(10\cdot \log(n^{30}))
=\Theta(300 \log(n))=\Theta(\log(n))$$
(Mmm)

I understand! (Nod) Thank you very much! (Smile)