What does it mean when f(n) is an element of O(g(n))?

Data Structures
1

Hi!

I know that f(n) = O(g(n)) means : 0 < f(n) <= c*g(n) such that c>0, n0>0 and for any n>= n0
but what does f(n) ∈ O(g(n)) mean? I’ve been given an example to solve: f(n) = 3log(n), g(n) = 9^n, f(n) ∈ O(g(n))

Could someone simply explain the meaning of f(n) ∈ O(g(n)) in this case, because I have no idea what I’m supposed to be solving for.

2

The symbol ∈ is the mathematical symbol for “is an element of” in set theory. In practice it means the same as = within the context of this question.

The Wikipedia page for Big O notation even mentions the interchangeable nature:

See Usage > Infinite asymptotics

Basically you are supposed to show that:

3*log(n) <= c*9^n

Or

log(n) <= k*9^n (where k = c/3, also a constant)

Note: This is not much of a computer science problem and more of a math problem, but I assume you already knew that.

1 Like
3

Thank you for the answer, this is all I was wondering about. It’s my first time here, sorry if I posted the wrong question

4

Not at all, there is a great portion of computer science that is owed to the background of mathematical theory and it is the heart of algorithmic complexity calculations. The reality of computer science is just that we cannot really express all algorithms in functional terms so we often end up in the world of approximations (hence why this is an engineering discipline rather than a theoretical / academic discipline).