-1

Could it be said that:

$f(x) = \Theta (g(x))$ if, for some large $x$, the functions $f(x)$ and $g(x)$ differ only by a constant scale factor, i.e. either $f(x) = \frac{g(x)}{C}$ or $f(x) = Cg(x)$, where $C = const$.

?

Could you help me define/explain it the simplest possible way?

Ziezi
  • 631
  • 2
    No. Please check the definition. https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations – Did Sep 19 '16 at 10:11
  • @Did yes, f(x) is bounded above and below by the same function g(x), i.e. g(x) is both smaller and larger, this what confuses me. – Ziezi Sep 19 '16 at 10:19
  • 1
    No, this is (not what your question says and) not what the definition says (either). – Did Sep 19 '16 at 10:35

1 Answers1

2

No you can not say that,

( consider an example that in a program code their are 1000 lines of code and by a true condition check 600 lines can be skipped than the minimum lines executed will be 400 and maximum line executed will be 1000. )

$f(x) = \Theta (g(x))$ this only gives you the idea that, $$ c_1g(n)\le f(n)\le c_2g(n) $$ this means for any value of n the minimum possibility is $c_1g(n)$ and maximum possibility is $c_2g(n)$. Consider an example where you have given $f(x) = \Theta (n)$ and you found that $$ 10n\le f(n)\le 10000n $$ then this means for any value of n the maximum possibility is $10000n$ it can not be equal to $1000000n^2$ for any n.

By assuming $f(n)=Cg(n)$ you are saying that it is fixed for all $n$ which is not the case. You can not find a single constant which satisfy the minimum and maximum possibility for complexity.

hardmath
  • 37,015
Sahil Kumar
  • 751