# Prove 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1

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.

• Your definition is missing (all I see is "[Click here to see definition]"). – Yuval Filmus Feb 23 '17 at 15:06
• 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.) – chi Feb 23 '17 at 16:21
• 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. – D.W. Feb 24 '17 at 2:44

## 1 Answer

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$.