What is a function $f(n)$ such that $t_n \in \Theta(f(n))$

Question

Let $t_n$ be defined as follows:

$$ t_n = \frac{571}{98}*7^n - \frac{45}{14}*5^n +\frac{6}{7}*n*5^n $$

I am looking for a function $f(n)$ such that $t_n \in \Theta(f(n))$.

I am confused at how I can find the $\Theta$

Can you please guide me?

Thanks

the biggest bound is $n*5^n$ and the lower bound is $5^n$. As I understand it, the $\Theta$ is a function that bound t(n) on the upper and lower side. but I can't see it here — lalaland, Sep 30 '21 at 20:41

score 2 · Accepted Answer · answered Sep 30 '21 at 20:50

2

Let $A, B, C$ be positive constants. Then since: $$ \lim_{n \to \infty} \frac{A \cdot 7^n - B \cdot 5^n + C \cdot n 5^n}{7^n} = A $$

it follows that $t_n \in \Theta(7^n)$.

answered Sep 30 '21 at 20:50

Adriano

Thank you. Can we therefore always use the biggest term of a function $t_n$ or it depends on the cases? – lalaland Oct 01 '21 at 14:40
1

Usually. In general, $f(n) + g(n) = O(\max{f(n), g(n)})$. – Adriano Oct 01 '21 at 17:58
yes but in the case of $\Theta$? – lalaland Oct 01 '21 at 20:23

1 Answers1