Be the first to answer - "Is it true that f(n)=O(g(n)) implies g(n)=O(f(n))"

robidEi8

Answered question

2022-12-05

Is it true that f(n)=O(g(n)) implies g(n)=O(f(n))

Dalia Cordova

Beginner2022-12-06Added 8 answers

The definition of the big-oh notation is as follows :

f (x) = O (g (x))

| f (x) | \leq c | g (x) |

for every big enough x and some constant c
This is why

f (x) = x

and

g (x) = x^{2}

is a counter-example :

x = O (x^{2})

because for example taking

c = 1

we have

x \leq x^{2}

for every

x \geq 1

x^{2}

can't be

O (x)

because that would mean that

x^{2} \leq c x

for every

x \geq x_{0}

x^{2} - c x \leq 0

but this is false because :

lim_{x \to \infty} x^{2} - c x = \infty

The usual intuition is that :

f (x) = O (g (x))

when

g (x)

grows faster than f(x)
This explains why

x = O (x^{2})

but the reverse isn't true .

Do you have a similar question?

Recalculate according to your conditions!

Didn't find what you were looking for?