So I am trying to work on a problem and honestly... I am so lost with this one. I will try to ask it the best I can.

Exact text of the problem: "Prove the following directly from the definition of Big Theta; 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1"

Additionally, the definition in question is [Click here to see definition]

Basically, I don't understand the definition and I don't understand the question. I understand that this chapter is talking about asymptotic behavior, and how given 2 different functions these 1 number could "grow" faster than the other up to a certain point and then it would switch. Example, Using 1 and 100,000,000 as n. In the following 2 functions 1 is larger number using 1... and then the other one is larger when you 100,000,000.

1,000,000n and n^2

Perhaps someone can help put the definition and question into words I can understand a little better.

  • 2
    $\begingroup$ Your definition is missing (all I see is "[Click here to see definition]"). $\endgroup$ – Yuval Filmus Feb 23 '17 at 15:06
  • 1
    $\begingroup$ The book should be more careful in that $10^8$ here is meant the constant function which always returns $10^8$, i.e. $\_ \mapsto 10^8$. Otherwise, the question would be asking to prove that a number belongs to a set of functions, which is puzzling. I find the text as written less natural and familiar than, say, "prove $10^8 = O(1)$", where the notational abuse is (IMHO) more common. (I mean: it pedantically defines $g(n)=1$ explicitly, but does not do so for $f(n)=10^8$. I'd suggest to avoid that.) $\endgroup$ – chi Feb 23 '17 at 16:21
  • $\begingroup$ It looks like you might have inadvertently created two accounts. I encourage you to merge your accounts so you retain the ability to comment on answers and edit your question. $\endgroup$ – D.W. Feb 24 '17 at 2:44

You haven't provided a definition, but here is a standard one:

Let $f,g$ be functions from $\mathbb{N}$ to $\mathbb{R}$. We say that $f(n) \in \Theta(g(n))$ (usually written $f(n) = \Theta(g(n))$) if there exist a natural number $N$ and positive real numbers $0 < a < b$ such that for all natural $n \geq N$ it holds that $$ ag(n) \leq f(n) \leq bg(n). $$

Roughly speaking, this says that the two functions $f,g$ have the same order of growth – they differ by a constant multiple. The definition is reflexive ($f(n) = \Theta(f(n))$), symmetric ($f(n) = \Theta(g(n))$ implies $g(n) = \Theta(f(n))$) and transitive ($f(n) = \Theta(g(n))$ and $g(n) = \Theta(h(n))$ imply $f(n) = \Theta(h(n))$), and so forms an equivalence relation. Each equivalence class is an "order of growth".

In your question, $f(n) = 10^8$ and $g(n) = 1$. So you have to find natural $N$ and positive reals $0 < a < b$ such that the following holds for all $n \geq N$: $$ ag(n) \leq f(n) \leq bg(n) \Longleftrightarrow a \leq 10^8 \leq b.$$ I'm sure you can find such $N,a,b$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.