1

When people explain Theta notation, they just start talking about a function T(n) without explaining what it is. Is it just a given function?

Why is it Theta(f(n)) instead of Theta(n)? Where did the f(n) come from? f(n) is usually a given function, then what is T(n)? Are they both? This is also not commonly explained.

All the explanations I find are all explained mathematically, but with consistent failure properly define things, and instead just start talking about things out of the blue.

Thanks, - A confused student

ahnbizcad
  • 10,491
  • 9
  • 59
  • 85
  • "When people explain Theta notation, they just start talking about a function T(n) without explaining what it is. Is it just a given function?" - Yes. That's the whole point: we are interested in it's complexity not it's explicit definition. – Mitch Wheat Jan 04 '15 at 08:08
  • 2
    T(n) is the time it takes to calculate a function F(n) – Benjamin Gruenbaum Jan 04 '15 at 08:09
  • That thread doesn't talk about T(n) or Theta(f(n)). – ahnbizcad Jan 04 '15 at 08:09
  • @Mitch Wheat When people start talking about things out of the blue, they also do that when introducing things with specific defintiions or conventiosn as well. If someone starts mentioning T(n) without explanation, but also starts mentioning O(f(n)) out of no where, an uninitiated person cannote tell the difference. The Big O has a particular meaning definition, while the T(n) is an arbitrary function... It's not hard to for explainers to go "Consider an arbitrary function T(n)..." – ahnbizcad Jan 04 '15 at 08:12
  • Then my question is how is T(n) different from f(n). Usually, g(n) is used for a second arbitrary function. I don't see why T(n) wouldn't have a meaning (like big O, Omega, and Theta do), especially since it's capitalized. Also, I don't think that semantically choosing T when talking about Theta and Theta only, is a coincidence, which is waht further confuses me... ;; Thanks for any clarification. VERY much appreciated – ahnbizcad Jan 04 '15 at 08:14
  • @Henry my question is very separate from what that question is asking. Big O vs Theta is not my question, but rather, Theta vs T(n) vs f(n) – ahnbizcad Jan 04 '15 at 08:15
  • @gwho getting a good understanding of Theta, O, Omega is the basis. It is hard to know what T(n) means without any context. Can you give an example of an explanation that uses T(n)? – Henry Jan 04 '15 at 08:18
  • @Henry all my sources start using it arbitrarily. here are some instances they use it in. "`T(n) = Theta(f(n))` IFF `T(n) = O(f(n)) and T(n) = Omega(f(n)). – ahnbizcad Jan 04 '15 at 08:22
  • @Henry ^ The above actually sounds like the definition of Theta. Maybe they're being sloppy with the naming semantics. My other book uses T(n) for arbitrary problems, indicating the book is using T(n) as arbitrary functions.... like f(n)... Does g(n) have a universal meaning, or is it too arbitrary? – ahnbizcad Jan 04 '15 at 08:24

0 Answers0