MHB Justify $\Theta(n^7 \log n)$ for $g(n)$

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion focuses on determining the asymptotic complexity of the function g(n) = 8n^7 log n + 18 log 13 + 16 log n^n + 12 n^(5/2). It is established that the dominant term is n^7 log n, leading to the conclusion that g(n) = Θ(n^7 log n). Participants verify this by showing that all other terms in g(n) are asymptotically smaller than n^7 log n for sufficiently large n. They confirm that for n ≥ 2, each term is less than or equal to n^7 log n, justifying the Θ notation. The discussion emphasizes the importance of identifying the dominant term and verifying the conditions for Θ notation.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! (Smile)

I want to find the asymptotic complexity ($\Theta$) of the function $g(n)=8n^7 \log n+18 \log{13}+16 \log n^n+12 n^{\frac{5}{2}}$.

We see that the dominant term is $n^7 \log n$, but how could we justify it? (Thinking)

Does this mean that : $g(n)=\Theta(n^7 \log n)$ ? :confused:
 
Technology news on Phys.org
According to definition we have to find constants such that

$$c_1 f(n) \leq g(n) \leq c_2 f(n) $$

is held true for all $n\geq N_0$ , Can you find such constants ?
 
ZaidAlyafey said:
According to definition we have to find constants such that

$$c_1 f(n) \leq g(n) \leq c_2 f(n) $$

is held true for all $n\geq N_0$ , Can you find such constants ?

Yes, but.. how can I explain that $n^7 \log n$ is the dominant term? (Thinking)
 
You can try to verify it by definition, that is,
$$g(n) = \Theta(n^7 \log n) \Leftrightarrow \exists c>0, \exists n_0 \in \mathbb{N}, \forall n \geq n_0: 0 \leq g(n) \leq c n^7 \log n$$

I would do the following: try to show that all terms (with exception of the first term obviously) of $g(n)$ are smaller than $n^7 \log n$ for a certain $n_0 \in \mathbb{N}$.

First, note that $\forall n \geq 2: 18 \log 13 \leq n^7 \log n$. This follows from the fact that $\log n$ and $n^7$ are increasing functions forall $n \in \mathbb{N}_0$.

Second, we can write $16 \log n^n = 16n \log n$. We want to search for which values of $n \in \mathbb{N}_0$ we have: $16 n \log n \leq n^7 \log n$ or equivalently $16 n \leq n^7$. Since $n^7$ increases much faster than $16n$ for the natural numbers (without zero) we can conlude that $\forall n \geq 2: 16n \leq n^7$, therefore $ \forall n \geq 2: 16n \log n \leq n^7 \log n$.

For the last term we can use a similar argument to show that $\forall n \geq 2: 12n^{\frac{5}{2}} \leq n^7 \log n$.

At this point we have shown that all terms are smaller than $n^7 \log n$.
What's the conclusion now?
 
At the beginning, before I verify that $g(n)=\Theta(n^7 \log n)$ can I just say the following?

We see that the dominant term of the function $g(n)$ is $n^7 \log n$, so: $g(n)=\Theta(n^7 \log n)$ ?

Or is there a better way to explain why we suppose that $g(n)=\Theta(n^7 \log n)$? (Thinking)
 
By definition

$$T(n) = \Theta( G(n) ) \, \implies \,\, \lim \frac{T(n)}{G(n)} \to c \, ; \,\, 0<c<\infty $$

Suppose that $f(n) = a(n) +g(n)$ where $a(n)$ is the dominant term so

$$\lim_{n \to \infty } \frac{a(n)+g(n)}{a(n)} = 1+ 0 = 1 $$

So $T(n) = \Theta (a(n)) \blacksquare $.
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...

Similar threads

Replies
24
Views
4K
Replies
1
Views
1K
Replies
15
Views
8K
Replies
7
Views
2K
Replies
17
Views
4K
Back
Top