Asymptotic tight bound question

  • Thread starter Thread starter gr3g1
  • Start date Start date
  • Tags Tags
    Bound
Click For Summary
SUMMARY

The discussion centers on determining whether the function \(3^{n+1}\) belongs to \(\Theta(3^{n})\). The user correctly identifies that to prove this, they must demonstrate the existence of constants \(c_1\), \(c_2\), and \(n_0\) such that \(c_1 \cdot 3^{n} \leq 3^{n+1} \leq c_2 \cdot 3^{n}\) for all \(n > n_0\). The conclusion is that the statement is TRUE, as appropriate constants can be found to satisfy the definition of big theta.

PREREQUISITES
  • Understanding of asymptotic notation, specifically big theta (\(\Theta\)) notation.
  • Familiarity with exponential functions and their growth rates.
  • Knowledge of mathematical proofs and inequalities.
  • Basic algebra skills to manipulate inequalities.
NEXT STEPS
  • Study the formal definitions of big O, big Omega, and big Theta notations.
  • Learn how to derive asymptotic bounds for various functions.
  • Explore examples of asymptotic analysis in algorithm complexity.
  • Practice proving asymptotic relationships with different functions.
USEFUL FOR

Students in computer science, particularly those studying algorithms and data structures, as well as educators teaching asymptotic analysis concepts.

gr3g1
Messages
71
Reaction score
0

Homework Statement



Hi,

I just have a basic question regarding an asymptotic tight bound question.

The question is :
TRUE / FALSE

http://latex.codecogs.com/gif.latex?3^{n+1} \text{ belongs to } \Theta(3^{n})

By definition of big theta:

c_{1}g(n) \leq f(n) \leq c_{2}g(n) \text { } \forall n > n0

So in my case, g(n) = 3^{n} \text{ and } f(n)=3^{n+1}

Therefore to prove this true, I should show a set of values for c1, c2, and n for the definition to hold true.

Is that correct?
 
Last edited by a moderator:
Physics news on Phys.org
anyone?
 

Similar threads

Least Upper Bound Property ⇒ Archimedean Principle
  • · Replies 1 ·
Replies
1
Views
2K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Rational epsilon-delta limit proof questions
  • · Replies 9 ·
Replies
9
Views
4K
Every subset of a finite set is finite
  • · Replies 1 ·
Replies
1
Views
2K
MHB Upper Bound of Sets and Sequences: Analyzing Logic
  • · Replies 3 ·
Replies
3
Views
5K
If a sequence is eventually bounded then it is bounded
  • · Replies 2 ·
Replies
2
Views
5K
Why is a finite sub-cover necessary for proving continuity implies boundedness?
  • · Replies 1 ·
Replies
1
Views
3K
Proving Properties of Bounded Sets in Real Numbers
  • · Replies 11 ·
Replies
11
Views
2K
Undergrad Two basic results from measure theory -- on volumes of rectangles
  • · Replies 2 ·
Replies
2
Views
3K
Prove limit comparison test for Integrals
  • · Replies 2 ·
Replies
2
Views
2K