Computer Science Asked by Rolodecks on December 8, 2020

Suppose the following is true for some f(n) and g(n):

$f(n) = Theta(g(n))$

Does that mean $f(n/k) = Theta(g(n))$ for any value of $k>0$?

I know that for the above to be true, there must exist positive constants $c_1$, $c_2$, $n_0$ such that for all $n geq n_0, $ $c_1(g(n)) leq f(n) leq c_2(g(n))$. Thus if $f(n) = Theta(g(n))$, then can I assume:

$frac{1}{k}c_1(g(n)) leq f(n/k) leq frac{1}{k}c_2(g(n))$ to satisfy big Theta?

My apologies if this is totally obvious or if I’m completely on the wrong track, my math background isn’t the strongest. Are there any relevant properties that might describe this relationship?

Take $f(n) = n^4$. For this function, if you double the argument, the result is multiplied by 16, that is by a constant factor. Now take $g(n) = 2^n$. For this function, if you double the argument, the result is squared, and since $2^n$ can grow arbitrarily large, there is no limit to the growth factor achieved by squaring g(n).

That’s the difference. If the growth from doubling the argument has an upper limit then $Theta$ stays the some, otherwise it doesn’t.

Correct answer by gnasher729 on December 8, 2020

For given $f(n)$, well defined, for $forall nin mathbb{N}$, the function $f(n/x)$ can be even undefined: for example $f(n)=frac{1}{n-frac{1}{2}}$ and $x=2$.

More sophisticated example is $$ f(n)=begin{cases} 2^k, & n=2k+1 \ k, & n=2k end{cases} $$ Obviously $f(2n) in Theta(n)$, but $f(n)notin Theta(n)$.

Case, where your sentence is true is, for example, homogeneous function with homogeneous degree $k=1$ i.e. when $g(Cx)=Cg(x)$ and we consider homogeneous functions subset from $Theta(g)$.

Answered by zkutch on December 8, 2020

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) in Theta(g(n))$ but $f(n / 2) notin Theta(g(n))$, so this does not hold in general.

Answered by Watercrystal on December 8, 2020

1 Asked on November 28, 2021 by user2207686

0 Asked on November 28, 2021

combinatorics formal languages regular languages strings word combinatorics

2 Asked on November 28, 2021

church turing thesis mu recursion turing completeness turing machines

0 Asked on November 25, 2021

2 Asked on November 25, 2021 by hish

finite automata pumping lemma regular expressions regular languages

5 Asked on November 23, 2021 by stephen-mwangi

1 Asked on November 23, 2021 by judy-l

3 Asked on November 21, 2021

functional programming higher order logic lambda calculus polymorphisms programming languages

0 Asked on November 21, 2021 by user3862410

algorithm analysis algorithms coding theory order theory ordering

1 Asked on November 21, 2021

2 Asked on November 17, 2021 by ocram

1 Asked on November 17, 2021 by user123521

1 Asked on November 17, 2021 by dshri

0 Asked on November 13, 2021 by northerner

1 Asked on November 11, 2021 by pragya

1 Asked on November 11, 2021 by yuezato

1 Asked on November 8, 2021 by john-flemin

2 Asked on November 5, 2021 by vinay-varahabhotla

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir