Questions tagged [big-theta]
6 questions
25
votes
2 answers
Why is Big O taught instead of Big Theta?
Big O notation provides an upper bound to a function whereas Big Theta provides a tight bound. However I find that Big O notation is typically (and informally) taught and used when they really mean Big Theta.
e.g. "Quicksort is O(N^2)" can turned…
tskuzzy
- 732
- 1
- 7
- 12
13
votes
3 answers
Please explain the statement that the function an+b belongs to O(n^2) and Θ(n)?
Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)?
I do not need mathematical rigor here. I need a programmers answer. Some logical way of explaining.
This is precisely why I…
Geek
- 5,107
- 8
- 40
- 58
11
votes
5 answers
Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?
I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's taking way too much time to do it by hand. it's…
Julien L
- 219
- 1
- 3
9
votes
5 answers
Theta notation on constant time. Why we use the 1?
In asymptotic notation when it is stated that if the problem size is small enough (e.g. n
user10326
- 1,834
- 3
- 17
- 18
1
vote
1 answer
Notation for the average time complexity of an algorithm
What notation do you use for the average time complexity of an algorithm? It occurs to me that the proper way would be to use big-theta to refer to a set of results (even when a specific try may differ). For example, average array search would be…
user2106285
- 43
- 4
-2
votes
2 answers
Difference between O(N^2) and Θ(N^2)
What is the difference between O(N^2) and Θ(N^2)? I know that O is the upper bound and Θ is tight bound. Could someone explain me this concept with an example.
Sgt. Foley
- 21
- 1
- 1
- 3