CODEWITHSUNDEEP
algorithmasymptotic-complexity
Aashi
Aashi

Reputation: 25

Functions in o(n) and ω(1)

I was solving some question and I came across this one.

Give a function which is both in o(n) (little-oh) and in ω(1) (little-omega), or state that none exists.

I thought of functions like logn or sqrt(n). However, I'm still doubtful whether such function will exist or not. Does a constant function make any difference

Upvotes: 1

Views: 81

Answers (1)

amit
amit

Reputation: 178491

You are correct.

Proof is based on set theory.

o(n) = O(n) \ Theta(n)
ω(1) = Omega(1) \ Theta(1)

You are looking for something that is in the intersection of o(n) and ω(1) log(n) is in O(n), and in Omega(1) - and not in Theta(n) nor Theta(1), so it is in the intersection, and thus fits.

Upvotes: 3

Related Questions