Big O notation question
Am i right to assume that the main difference between Big O o(n) and Big O o(1) is the fact that Big O o(n) uses a loop to iterate and Big O o(1) does not? I know that Big O o(n) depends on the amount of time the function iterates as in Big O o(1) is the opposite function will not change dependent on the number of elements in the function.
O(anything) is a mathematical limit that we can impose on the function from the definition of big O
https://en.wikipedia.org/wiki/Big_O_notation
http://web.mit.edu/16.070/www/lecture/big_o.pdf
A lot of computer science courses do not stress this common mistake enough:
https://en.wikipedia.org/wiki/Big_O_notation
http://web.mit.edu/16.070/www/lecture/big_o.pdf
A lot of computer science courses do not stress this common mistake enough:
| A common error is to confuse these by using O when Θ is meant. For example, one might say "heapsort is O(n log n)" when the intended meaning was "heapsort is Θ(n log n)". Both statements are true, but the latter is a stronger claim. |
Last edited on
Big O is a fairly tight bound.
Little O is a very loose bound.
What it means is, given some function g(x), that for any x, g(x) is pretty close to O(x):
g(x) ≤ O(x)
For Little O the bound is loosened significantly. For any x, g(x) is definitely less than o(x):
g(x) << o(x)
Big-O is really all you need for a lot of algorithms. For example, given a sorting algorithm, you really don't care if specific cases sort faster than Big-O indicates. That's great, but what matters is when someone gives you bad data. What's the worst-case behavior?
Sometimes it does matter in other directions. That's what theta and omega are for.
Theta is a bound on both the upper and the lower. Simplistically, you can say it is like:
g(x) = Θ(x) [That's a capital Theta]
And again, Little-theta is just a lot more loose:
g(x) ≈ θ(x) [That's a miniscule theta]
Omega is the opposite of O: it measures the best case behavior:
g(x) ≥ Ω(x)
And again, Little-omega is a lot more loose:
g(x) >> ω(x)
g(x) may differ from f(x) by some constant value, so those aren't hard equalities in there.
Hope this helps.
Little O is a very loose bound.
What it means is, given some function g(x), that for any x, g(x) is pretty close to O(x):
g(x) ≤ O(x)
For Little O the bound is loosened significantly. For any x, g(x) is definitely less than o(x):
g(x) << o(x)
Big-O is really all you need for a lot of algorithms. For example, given a sorting algorithm, you really don't care if specific cases sort faster than Big-O indicates. That's great, but what matters is when someone gives you bad data. What's the worst-case behavior?
Sometimes it does matter in other directions. That's what theta and omega are for.
Theta is a bound on both the upper and the lower. Simplistically, you can say it is like:
g(x) = Θ(x) [That's a capital Theta]
And again, Little-theta is just a lot more loose:
g(x) ≈ θ(x) [That's a miniscule theta]
Omega is the opposite of O: it measures the best case behavior:
g(x) ≥ Ω(x)
And again, Little-omega is a lot more loose:
g(x) >> ω(x)
g(x) may differ from f(x) by some constant value, so those aren't hard equalities in there.
Hope this helps.
ok, thank you guys for your replies...I can tell you are subject matter experts and very intelligent...But, you talking to a novice whom is just started to work on data structures today. mind you im doing this at home, myself...So the way you are explaining this stuff to me is overwhelming and essentially another language. i just wanted a simple dumbed down answers to my question.
The lecture notes from mit (that I posted a link to) approach the subject slower than wikipedia does.
What I've done is about as simple as it gets -- What's left is some basics you are missing.
functions
A function takes some number and produces another. It can be defined any way you like. How about a common function, like sine?
sine(0) → 0
sine(π) → 0.0548...
sine(2π) → 0.109...
etc.
When you plot that on a graph, you get the famous wavy line:
https://www.google.com/search?q=sine&s=&search=pi&tbm=isch&gws_rd=ssl
Here are some other very useful functions:
f(x) = x (linear)
f(x) = log x (logarithmic)
f(x) = x² (quadratic)
Using a function g(x) to measure performance
The way that a function performs can be graphed. However, the exact performance depends on a lot of things, and it is not practical to be that specific. And, typically, we are interested in performance based on how many things the function is operating on.
For example, a sorting algorithm like bubble sort is pretty quick with only ten or so things to sort. But once you get 500, or 10000, then it is too slow to be useful. When we are comparing sorting algorithms, we are interested in how it performs based on how many items it has to sort. That is, our function g(x), which is our magic function that describes how bubble sort works with N items, tells us how much time/memory/whatever-you-are-measuring it takes to use bubble sort on N items.
Bubble sort is a quadratic (n²) function in the worst case. Given 10 items, it will take 100 'operations' to sort. Given 500 items, it will take 250000 'operations'. It gets worse as n² gets worse.
O/Θ/Ω Notation
Now, a well-written bubble sort performs best if the array is already sorted (because it knows that it should quit after the first pass). It performs worst if the array is the exact opposite of sorted (sorted in reverse order). So for some inputs the bubble sort performs better (faster/less memory/etc) and for some inputs the bubble sort performs worse -- even if N has not changed.
What this means is that g(x) can vary pretty widely for a single N.
In fact, the g(x) function can be so complicated that it isn't worth writing it out. (Or even understanding it!)
Part of the problem is that the g(x) may be different depending on things the programmer cannot control easily: hardware, compiler, OS, number of neutrinos passing through the chip, etc. It is not useful to talk about g() directly.
But we can tell things about the best and the worst behaviors of g(). That's where the O(n) comes in:
O(n) tells us that wherever the fuzzy value we get from g(n) is, it is always under O(n) on the graph.
(Sorry I don't have better pictures.)
The Big-O says that the function given in parentheses [O(n) → f(n)=n → linear] is very close to the largest value you'll get from g(n) for that specific n.
A Little-o means that the g() is somewhere way below f(n)=n:
Theta would put a line right through the middle of that fuzziness from g(x).
Omega would put a line underneath all the fuzziness from g(x).
Hope this helps.
functions
A function takes some number and produces another. It can be defined any way you like. How about a common function, like sine?
sine(0) → 0
sine(π) → 0.0548...
sine(2π) → 0.109...
etc.
When you plot that on a graph, you get the famous wavy line:
https://www.google.com/search?q=sine&s=&search=pi&tbm=isch&gws_rd=ssl
Here are some other very useful functions:
f(x) = x (linear)
f(x) = log x (logarithmic)
f(x) = x² (quadratic)
Using a function g(x) to measure performance
The way that a function performs can be graphed. However, the exact performance depends on a lot of things, and it is not practical to be that specific. And, typically, we are interested in performance based on how many things the function is operating on.
For example, a sorting algorithm like bubble sort is pretty quick with only ten or so things to sort. But once you get 500, or 10000, then it is too slow to be useful. When we are comparing sorting algorithms, we are interested in how it performs based on how many items it has to sort. That is, our function g(x), which is our magic function that describes how bubble sort works with N items, tells us how much time/memory/whatever-you-are-measuring it takes to use bubble sort on N items.
Bubble sort is a quadratic (n²) function in the worst case. Given 10 items, it will take 100 'operations' to sort. Given 500 items, it will take 250000 'operations'. It gets worse as n² gets worse.
O/Θ/Ω Notation
Now, a well-written bubble sort performs best if the array is already sorted (because it knows that it should quit after the first pass). It performs worst if the array is the exact opposite of sorted (sorted in reverse order). So for some inputs the bubble sort performs better (faster/less memory/etc) and for some inputs the bubble sort performs worse -- even if N has not changed.
What this means is that g(x) can vary pretty widely for a single N.
In fact, the g(x) function can be so complicated that it isn't worth writing it out. (Or even understanding it!)
Part of the problem is that the g(x) may be different depending on things the programmer cannot control easily: hardware, compiler, OS, number of neutrinos passing through the chip, etc. It is not useful to talk about g() directly.
But we can tell things about the best and the worst behaviors of g(). That's where the O(n) comes in:
O(n) tells us that wherever the fuzzy value we get from g(n) is, it is always under O(n) on the graph.
O(n) │ / │ / ░░░░ g(n) │ / ░░░ │ / ░░░ │ / ░░ │/ ░ ┼───────────────── |
The Big-O says that the function given in parentheses [O(n) → f(n)=n → linear] is very close to the largest value you'll get from g(n) for that specific n.
A Little-o means that the g() is somewhere way below f(n)=n:
o(n) │ / │ / ░░░░ g(n) │ / ░░░ │ / ░░░ │ / ░░ │/ ░░ ┼───────────────── |
Theta would put a line right through the middle of that fuzziness from g(x).
Omega would put a line underneath all the fuzziness from g(x).
Hope this helps.
Topic archived. No new replies allowed.