CODEWITHSUNDEEP
algorithmfunctiontime-complexitybig-obelongs-to
Daniel Bustamante
Daniel Bustamante

Reputation: 1

Is this formulation O(n) ∈ O(f) correct?

Is this formulation O(n) ∈ O(ƒ) correct?

My answer is yes, because the O(n) complexity can belong to O(ƒ) if O(ƒ) > O(n) (for example if O(ƒ) = n log n). That is to say, the complexity O(n) can be part of the set described by O(ƒ) if O(ƒ) is an upper bound of O(n). However I'm not 100% sure.

Upvotes: -1

Views: 113

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

"∈" means "element of", and so your formulation is not correct.

O(n) is a set of functions, and O(f) is a set of functions. O(n) cannot be an element of O(f), because O(f) is not a set of sets.

If you want to say that "O(n) is a subset of O(f) or the same set", you write it "O(n) ⊆ O(f)".

Upvotes: 1

Related Questions