1

Please excuse me if this is a stupid question, but I want to make sure. I was thinking log n is in between of the n and 1 so maybe it could work too. or we can call it theta (log n) only when the function is O(log n ) and big omega(log n ) ?

james kim
  • 33
  • 5
  • related? https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent – nahzor Jun 21 '17 at 16:13

1 Answers1

1

No, O means "faster than or equal to" and Ω means "slower than or equal to". So f could still be Ɵ(1) or Ɵ(n). Also, there are an infinite number of complexity classes between the bounds, such as Ɵ(log log n).

c2huc2hu
  • 2,447
  • 17
  • 26