Win a copy of Transfer Learning for Natural Language Processing (MEAP) this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Paul Clapham
  • Devaka Cooray
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Liutauras Vilda
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Piet Souris
Bartenders:
  • salvin francis
  • Carey Brown
  • Frits Walraven

combining big Oh with bit Theta

 
Ranch Hand
Posts: 407
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys : I've noticed that in some proofs, they combine big Oh notation with big Theta.... I'm not sure, in general, why you would want to express the Upper bound (big Oh) of an algorithm in terms of the lower bound (big theta).....

Any thoughts on the combination of big Oh, horseshoe Oh, and Theta Oh in algorithm analysis ?
 
Saloon Keeper
Posts: 11898
253
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Theta is not lower bound. Omega (or horseshoe, as you call it) is the lower bound. If an algorithm is in Theta for some function, it means that the lower bounds and the upper bound are both described by that function as well.

For instance, if an algorithm is in O(n log n), and it is in Omega(n log n) as well, we say the algorithm is in Theta(n log n).
 
jay vas
Ranch Hand
Posts: 407
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmmm okay... So I guess a "tight" bound is when omega=theta ?
 
Stephan van Hulst
Saloon Keeper
Posts: 11898
253
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A bound g(n) is tight if it's in O(f(n)) and Omega(f(n)) and thus in Theta(f(n)).
 
Paper jam tastes about as you would expect. Try some on this tiny ad:
Two software engineers solve most of the world's problems in one K&R sized book
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    Bookmark Topic Watch Topic
  • New Topic