0

For an assignment, I have the following question:

For all functions $\;f, g : \mathbb{N} \to \mathbb{R}^+$ from positive integer numbers to nonnegative real numbers, let the running time $T(n)$ of an algorithm be $\Theta(f(n))$, and $f(n)$ be a function of $n$ that is $\;\Theta(g(n))$. Using the definitions of asymptotic notations, prove that $T(n)$ is $\;\Theta(g(n))$.

I dont want the answer to this I just need some insight. I'm having trouble understanding what its exactly asking me to do and how I should go about solving this. Thank you.

quapka
  • 1,466
  • 9
  • 21
Marko
  • 1

1 Answers1

0

Follow the definition of $\Theta(f(n))$, in particular $T(n)=\Theta(f(n))$ if and only if $T(n)=O(f(n))$ and $T(n)=\Omega(f(n))$. Do the same thing with $f(n)=\Theta(g(n))$, then you'll see how you can move on to a full proof.

Alt
  • 2,592