-3
$\begingroup$

Hi i am practising standard theta notation:

How could i find the standard theta notation of the following :

  • 2n + 3n^2(log n)^3 + 2 and
  • ((2n^2 + 7n+5)(7n+1))/7

So far i have used the "drop constants and find dominating term" strategy where we remove the constants from the expressions and then we find the biggest and dominating value and i got:

  • Θ(n^2(logn)^3) and
  • Θ(n^2) respectively, however i am not sure if this is correct, could someone please help me out. Thank you.
Improve this question
$\endgroup$
3
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Feb 5 at 0:52
  • $\begingroup$ Please do not deface your question by replacing it with nonsense. $\endgroup$
    – D.W. ♦
    Feb 13 at 0:06
  • $\begingroup$ Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work? $\endgroup$
    – Glorfindel
    Feb 13 at 17:37

2 Answers 2

Reset to default
1
$\begingroup$

Perform this test:

  • does $\dfrac{2n + 3n^2\log^3 n + 2}{3n^2\log^3n}$ tend to a constant ?

  • does $\dfrac{(2n^2 + 7n+5)(7n+1)}{n^2}$ tend to a constant ?

Improve this answer
$\endgroup$
3
  • $\begingroup$ i dont understand please elaborate $\endgroup$
    – zeek
    Feb 5 at 11:08
  • $\begingroup$ I hate to nitpick, but 2+sin(n) = Θ(1), yet (2+sin(n))/1 does not tend to a constant. $\endgroup$
    – Stef
    Feb 5 at 11:26
  • 1
    $\begingroup$ @Stef: tending to a constant is a sufficient condition. I knew that someone would nitpick. $\endgroup$
    – Yves Daoust
    Feb 5 at 14:12
0
$\begingroup$
  • First Expression: $2n + 3n^2(log n)^3 + 2$ is indeed correct.
  • Second Expression: $\dfrac{(2n^2 + 7n+5)(7n+1)}{7}$ is not correct. The leading expression of the second expression is $\dfrac{14}{7}$$n^3$ and not $2n^2$. It seems that you missed multiplying the two expressions by each other. Which give you the following: $\dfrac{14n^3 + 51n^2 + 42n + 5}{7}$. Thus, the leading expression is $\dfrac{14n^3}{7}$$=2n^3$.

Thus, the second expression would give you that it is $\Theta(2n^3)$.

I'd like to advise you to read more about the formal definition of the function $\Theta$, which requires you to know about the formal definitions of both $O$ and $\Omega$. In the expressions you gave, proving $\Theta(g(n))$ is easy. However, in many other expressions and algorithms , proving that $f(n) = \Theta(g(n))$ isn't easy. It would require you to prove both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.