Big O notation - Aho, Hocraft and Ullman
arnuld
Ullman, Page 31, Example 1.4
Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
see that T(n) is O(n^2) .
I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
if this discussion of the authors is only theoretical. I mean if can
understand Data Structures and Algorithms and write code without
understanding this section, then please tell me, I will leave it as its f
no use at a practical level.
--
www.lispmachine.wordpress.com
my email is @ the above blog.
Pascal J. Bourguignon
> This is from "Data Structures and Algorithms" by Aho, Hopcraft and
> Ullman, Page 31, Example 1.4
>
> Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
> see that T(n) is O(n^2) .
>
> I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
That's the very point of the O(.) equivalence classes!
It doesn't matter whether you're considering n or n+1, the question is
that you're on the same curve, the square curve, and that sooner or
later you will go beyond resources.
Well, on a square curve you will go beyond resources much sooner than
on a linear curve. And on an exponential curve, you'll go beyond
resources much much much sooner.
Read again http://en.wikipedia.org/wiki/Big_O_notation
T(n) = O(n²) as n->∞
<=> ∃M∈ℝ, ∃n₀∈ℝ, ∀n, n>n₀ => |T(n)| ≤ M|n²|
Now, T(n) = (n+1)² = n²+2n+1 ≤ n²+2n²+1n² = 4n², so you can take M=4, and
∃n₀∈ℝ, ∀n, n>n₀ => |T(n)| ≤ 4|n²|
=> ∃M∈ℝ, ∃n₀∈ℝ, ∀n, n>n₀ => |T(n)| ≤ M|n²|
> if this discussion of the authors is only theoretical. I mean if can
> understand Data Structures and Algorithms and write code without
> understanding this section, then please tell me, I will leave it as it IS OF
> no use at a practical level.
Yes, it is of use at a practical level. Being able to do complexity
analysis on your algorithms, will let you know whether your program
will have enough time and enough memory to process the user data.
It can always work on the two or three data items you use in your
tests. But what will happen when the users will feed it a thousands,
a million or a billion data items to process? Will it still be as
fast and and thrifty, or will it need 500 ExaBytes of RAM and 15
billion years of processing time?
--
__Pascal Bourguignon__
Richard Heathfield
> This is from "Data Structures and Algorithms" by Aho, Hopcraft and
> Ullman, Page 31, Example 1.4
>
> Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then
> we see that T(n) is O(n^2) .
I assume you mean that T() is a function - something like:
fun T(integer n)
integer d = n + 1
yield d * d
nuf
> I did not get the last line. If T(n) = (n+1)^2 , how it can be
> deduced that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
Big-O is a rough-and-ready measure of worst-case workload in relation
to the amount of data that must be processed.
Multiply 123 by itself *by hand*, showing all your working and taking
no shortcuts, and count how many separate multiplications you have to
do. Now repeat the process for a four-digit number, eg 9287. Then do
it for a five-digit number, and so on up to ten digits or so. Plot
your results in a graph, and observe the shape of that graph.
For 123, for example (and remember we are not taking any shortcuts),
we need to multiply 3 * 3, 3 * 2, 3 * 1, 2 * 3, 2 * 2, 2 * 1, 1 * 3,
1 * 2, and 1 * 1. We also need some shifts and adds, but never mind
those. Nine multiplications for a datum three digits wide. For four
digits, we have to do sixteen multiplications. And so on.
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
Patricia Shanahan
> This is from "Data Structures and Algorithms" by Aho, Hopcraft and
> Ullman, Page 31, Example 1.4
>
> Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
> see that T(n) is O(n^2) .
>
> I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
The big-O notation classifies functions such as T(n) according to their
behavior as n increases. The book is not asserting that n^2 and (n+1)^2
are equal, but that (n+1)^2 is in the set of functions defined by
O(n^2). The difference between n^2 and (n+1)^2 becomes relatively
unimportant as n increases.
> if this discussion of the authors is only theoretical. I mean if can
> understand Data Structures and Algorithms and write code without
> understanding this section, then please tell me, I will leave it as its f
> no use at a practical level.
You need to understand it. It abstracts and simplifies very important
aspects of algorithm performance.
Patricia
[Jongware]
> arnuld <sun...@invalid.address> writes:
>
>> It can always work on the two or three data items you use in your
>> tests. But what will happen when the users will feed it a thousands,
>> a million or a billion data items to process? Will it still be as
>> fast and and thrifty, or will it need 500 ExaBytes of RAM and 15
>> billion years of processing time?
So ... with Moore's (heuristic) law, would that still be a problem in
another 5 years?
----
[Jw] | Joking, of course -- I grok O(n).
Beej Jorgensen
>I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
>that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
One way to think of this is that you're usually interested in how well
an algorithm scales when n gets large, and when n is large, n^2 and
(n+1)^2 become more and more identical.
>if this discussion of the authors is only theoretical. I mean if can
>understand Data Structures and Algorithms and write code without
>understanding this section, then please tell me, I will leave it as its f
>no use at a practical level.
I'm going to go with "you really should understand this".
I was on a project (I was doing the front-end, another guy was doing the
back end), and things were working swimmingly--until we opened the site
for beta. As soon as we got about 2000 registered users, the DB died
under the load. Now, mind you, this wasn't 2000 simultaneous
users--this was just 2000 users registered.
I never found out exactly what was happening in the back-end code, but I
suspect there was some kind of O(N^2) process (or worse) running back
there. It was fixed, and the site went on to get 100K or so users
during its short lifespan (it was a site to market another product.)
But you have my sympathies, because there's so much completely accurate
instruction on this topic that is utterly impenetrable to most
newcomers. (In their defense, it is a difficult concept to present
well.) Here are a few links that seem popular and not too bad (I only
skimmed them):
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
http://www.perlmonks.org/?node_id=573138
http://www.perlmonks.org/?node_id=227909
HTH,
-Beej
Michael Ekstrand
> This is from "Data Structures and Algorithms" by Aho, Hopcraft and
> Ullman, Page 31, Example 1.4
>
> Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
> see that T(n) is O(n^2) .
>
> I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
As mentioned in other replies, O(n) notation is an approximation to tell
you the general order of the growth of a function. If you expand
(n+1)^2, you get n^2+2n+1. In general, if you have a polynomial
function, it is big-O of its term of highest degree with coefficient
dropped; thus this function is O(n^2). Think of O as "order of" or
"grows about as fast as". That's what it means at a practical level.
More formally, though, it helps to review the definition of O(n):
A function f(n) is O(g(n)) iff there is some c and m such that for all
n>=m, f(n) <= c*g(n).
If we multiply out (n+1)^2, we get T(n)=n^2+2n+1. Let this be f(n) in
the definition. Let g(n)=n^2. Now, let us set c=2 and m=3. f(3) =
T(3) = 9+6+1 = 16. 2*g(3) = 18. Thus f(3) <= 2*g(3). This will be true
for all n>3 -- at n=3, 2*n^2 overtakes (n+1)^2, and the latter never
catches up.
> if this discussion of the authors is only theoretical. I mean if can
> understand Data Structures and Algorithms and write code without
> understanding this section, then please tell me, I will leave it as its f
> no use at a practical level.
Can you implement data structures? Sure. Can you understand their
performance implications? Not nearly as well as you can if you
understand big-O (asymptotic) notation. I'd advise you not to skip this
portion; that shortcut will only hamper your understanding of what's
going on. It may not seem like it matters, but understanding this lets
you better understand and explain your algorithms and communicate with
others about them.
- Michael
Kelsey Bjarnason
Explanation by example. Let's take five values, 10, 100, 1,000, 10,000
and 100,000 and compare O(n) and O(n)^2:
N O(n) O(n)^2
10 10 100
100 100 10,000
1,000 1,000 1,000,000
10,000 10,000 100,000,000
100,000 100,000 10,000,000,000
Note that while n has increased only by a factor of 10,000, O(n)^2 has
increased by a factor of 100,000,000.
Ponder that in terms of, say, sorting a database. If you can process
1,000 records per second, for 100,000 records an O(n) algorithm would
take 100 seconds, while an O(n)^2 algorithm would take about 115 days.
It really makes very little difference whether you're dealing with O(n)^2
or O(n+1)^2 or O(359,000 * n)^2; as n goes up, all the other factors -
such as the +1 - are simply swamped by the massive increase due to the ^2.
Or, in other words, the difference between 10,000,200,001 (100,000+1^2)
and 10,000,000,000 (100,000^2) is completely inconsequential, as you'll
have long since been fired for using the wrong algorithm to sort the
company's data.
So what he's saying is that in the general case examined, where T(n) = (n
+1)^2, the +1 is irrelevant; T is an O(n)^2 function. Not that n = n+1,
just that the +1 simply doesn't matter. At small n, it is generally
inconsequential because you're processing a small number of items, while
at large n it is inconsequential because the effects of the ^2 completely
dwarf it.
Willem
) This is from "Data Structures and Algorithms" by Aho, Hopcraft and
) Ullman, Page 31, Example 1.4
)
) Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
) see that T(n) is O(n^2) .
)
) I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
) that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
The definition of big-O is basically something like this:
f() is in O(g()) iff f(n) <= C*g(n) for all n >= N
Where C and N are suitable constants.
In the case of T(n) = (n+1)^2, the constants could be C = 2 and N = 2:
(n+1)^2 = n^2 + 2n + 1, so the difference between that and 2n^2 is
n^2 - 2n - 1, which is positive for n >= 2.
Usually, to get to big-O from any function, you follow some simple steps.
One of them is that any polynomial is in the big-O of n^x where x is the
degree of the polynomial.
In most normal cases, you only have to worry about n, n^2 or n^3 and
perhaps a factor of log(n) multiplied in.
Sometimes you have O(2^n) which is really really bad.
) if this discussion of the authors is only theoretical. I mean if can
) understand Data Structures and Algorithms and write code without
) understanding this section, then please tell me, I will leave it as its f
) no use at a practical level.
The practical use is in knowing that it is usually orders of magnitude more
significant if you can improve the big-O performance of an algorithm than
if you can improve it by some constant factor.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Ben Bacarisse
> On Mon, 31 Aug 2009 11:27:15 +0000, arnuld wrote:
>
>> This is from "Data Structures and Algorithms" by Aho, Hopcraft and
>> Ullman, Page 31, Example 1.4
>>
>> Suppose T(0) = 1 and T(1) = 4, and in general T(n) = (n+1)^2 . Then we
>> see that T(n) is O(n^2) .
>>
>> I did not get the last line. If T(n) = (n+1)^2 , how it can be deduced
>> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
>>
>> if this discussion of the authors is only theoretical. I mean if can
>> understand Data Structures and Algorithms and write code without
>> understanding this section, then please tell me, I will leave it as its
>> f no use at a practical level.
>
> Explanation by example. Let's take five values, 10, 100, 1,000, 10,000
> and 100,000 and compare O(n) and O(n)^2:
>
> N O(n) O(n)^2
> 10 10 100
> 100 100 10,000
> 1,000 1,000 1,000,000
> 10,000 10,000 100,000,000
> 100,000 100,000 10,000,000,000
>
> Note that while n has increased only by a factor of 10,000, O(n)^2 has
> increased by a factor of 100,000,000.
Maybe a small point, but I don't know what O(n)^2 means. I'd assume a
typo for O(n^2) if you did not repeat the pattern a few times below.
Knowing you to be a careful poster, I would guess that it is the set
{ g(x) = (f(x))^2 for some f in O(n) }.
Regardless, I think it is unwise to label a column of numbers with
something that denotes a set of functions.
> Ponder that in terms of, say, sorting a database. If you can process
> 1,000 records per second, for 100,000 records an O(n) algorithm would
> take 100 seconds, while an O(n)^2 algorithm would take about 115
> days.
Some O(n) algorithms might take 1s or 1000s. Since I am not sure what
O(n)^2 means I won't comment on the relationship.
If the cost function, f, for some algorithm is in "seconds of runtime"
you can say what f(1000) is but you can't say much about the values of
any of the other functions in O(f); and you can't talk about the time
taken by an O(n) algorithm. (I know you are simplifying to help
explain, but I think you have simplified away exactly what big-O is
all about.)
I don't think you can get away from the fact that an algorithm's cost
has to be expressed as an actual function of something like
comparisons, data swaps, array accesses, whatever, and that we then
categorise that function as belonging to some class of functions by
writing a minimal big-O class for it. (I say minimal because O(n+1) =
O(34 * n) = O(n) so it makes sense to use O(n) as the one we write.)
Once you've done this you can't talk about the cost anymore. You
can't even talk about the relative cost of an O(n) algorithm vs. a
O(n^2) one. What you gain is a characterisation of the algorithm that
is eliminates all the practical details that make the performance of
algorithms hard to compare in practise.
This is what AH&U are doing. They have an exact formula for T(n) (it
is (n+1)^2) and they characterise T by saying that T is in O(n).
> It really makes very little difference whether you're dealing with O(n)^2
> or O(n+1)^2 or O(359,000 * n)^2; as n goes up, all the other factors -
> such as the +1 - are simply swamped by the massive increase due to the ^2.
>
> Or, in other words, the difference between 10,000,200,001 (100,000+1^2)
> and 10,000,000,000 (100,000^2) is completely inconsequential, as you'll
> have long since been fired for using the wrong algorithm to sort the
> company's data.
That's a much clearer example: once you are squaring, f(n) ~= f(n+1)
when n gets large ("~=" meaning "approximately equal to").
> So what he's saying is that in the general case examined, where T(n) = (n
> +1)^2, the +1 is irrelevant; T is an O(n)^2 function. Not that n = n+1,
> just that the +1 simply doesn't matter. At small n, it is generally
> inconsequential because you're processing a small number of items, while
> at large n it is inconsequential because the effects of the ^2 completely
> dwarf it.
Ack.
--
Ben.
Kelsey Bjarnason
On Wed, 02 Sep 2009 14:57:32 +0100, Ben Bacarisse wrote:
> Maybe a small point, but I don't know what O(n)^2 means. I'd assume a
> typo for O(n^2) if you did not repeat the pattern a few times below.
An issue of clarity, perhaps:
O(n^2), O(n+1^2)... er... umm... isn't squaring 1 kinda pointless?
O(n)^2, O(n+1)^2, O(314259+n*57.2)^2...
Ben Bacarisse
> [snips]
>
> On Wed, 02 Sep 2009 14:57:32 +0100, Ben Bacarisse wrote:
>
>> Maybe a small point, but I don't know what O(n)^2 means. I'd assume a
>> typo for O(n^2) if you did not repeat the pattern a few times below.
>
> An issue of clarity, perhaps:
>
> O(n^2), O(n+1^2)... er... umm... isn't squaring 1 kinda pointless?
Sure, but I don't think anyone has written O(n+1^2). I think you are
suggesting that O(n+1)^2 is cleared than O((n+1)^2) but i don't think
introducing a non-standard notation assists clarity!
> O(n)^2, O(n+1)^2, O(314259+n*57.2)^2...
I still don't know what it means. Is O(n)^2 = O(n^2)?
--
Ben.
Kelsey Bjarnason
Yes
Alf P. Steinbach
O(g(n)), "big O" notation, means two different things depending on context.
The less strict meaning is an upper bound when n is large enough. Thus, if f(n)
is said to be O(g(n)), then with this meaning f(n) <= K*O(g(n)) for some
constant K when n is above some (unspecified) value. And instead of writing that
in full, some academics use a *one way equality* and just write f(n) = O(g(n)).
For example, 45*n^2 + 3n -102 <= K*(n^2) for some K when n is above some value.
And so one says that 45*n^2 + 3n -102 "is" (bounded by) O(n^2).
However, with that meaning, which happens to be the one in the formal notation,
it is also correct to say that 45*n^2 + 3n -102 "is" (bounded by) O(n^3), say...
A more strict and generally more practically useful meaning is an upper bound
*and* a lower bound.
This usage, which is common in Usenet postings and informal programmer speak,
corresponds in more formal notation to use of the greek uppercase omega instead
of "O" -- but many common character sets lack the uppercase omega.
Cheers & hth.,
- Alf
Nick Keighley
"There is nothing as practical as a good theory."
a "slow" sort may be O(n^2) which is fine for, say, 20 items
but as you get to hundreds or millions then you want a "faster"
sort say O(n log n).
Certain algorithms are known to be very slow O(m^n) and cryptography
relies on certain problems being practically impossible to solve.
If it takes years of super-computer time to break an encryption
then you're safe for a while (I assume they pick numbers that come
out in decades even allowing for Moore's law).
Having a rough idea of the speed of your algorithm is important.
Good algorithm selction is more important than micro-optimisation
tricks (which is better n*2, n<<1 or n+n? the answer is usually "who
cares?")
Ben Bacarisse
Sure, but I am not sure why you say this here in response (apparently)
to my question about KB's non-standard notation. It was the squaring
of a set that was curious to me.
> A more strict and generally more practically useful meaning is an
> upper bound *and* a lower bound.
>
> This usage, which is common in Usenet postings and informal programmer
> speak, corresponds in more formal notation to use of the greek
> uppercase omega instead of "O" -- but many common character sets
> lack the uppercase omega.
I was going to say that I call this less strict precisely because it
has it's own symbol, but then I realised you mean "more strict" as in
"tighter bound" and not as in "more formal"!
Yes, most people use O(n^2) to mean, informally, "can be this bad and
is no worse in the long run" but the context was that of a question
about AH&U's usage with is reasonably formal and quite precise.
--
Ben.
Andrew Tomazos
> If T(n) = (n+1)^2 , how it can be deduced
> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
What is the ratio between n^2 and (n+1)^2 when n is really big?
The ratio is about 1, right?
Say for example n = 1,000,000
Then n^2 = 1,000,000 ^ 2 = 1,000,000,000,000
And (n+1)^2 = (1,000,000 + 1) ^ 2
= 1,000,001 ^ 2 = 1,000,002,000,001
So the ratio is:
1,000,002,000,001 / 1,000,000,000
= 1.000002000001
Pretty darn close to 1. In fact as n gets larger and larger, the
ratio gets closer and closer to 1.
So if we are only interested in the expression when n is large, we can
simplify (n+1)^2 and just call it about n^2. It's easier to think
about.
That is all this "big O" notation is saying.
"f(n) = O(g(n))" just means that when n is large, the ratio between f
and g is about constant.
We usually don't need to calculate the time performance of an
algorithm to the millisecond. Usually we just need ballpark figures.
The study of "big O" notation gives us a tool to calculate those
ballpark figures quicker than calculating the exact ones.
That should provide sufficient motivation to understand *why* we are
studying this. The process of taking an expression and finding a
simpler asymptotically equivalent one is something that comes from
practice, I think best by working through several examples out of a
textbook.
-Andrew.
Robert Maas, http://tinyurl.com/uh3t
> >> tests. But what will happen when the users will feed it a thousands,
> >> a million or a billion data items to process? Will it still be as
> >> fast and and thrifty, or will it need 500 ExaBytes of RAM and 15
> >> billion years of processing time?
> So ... with Moore's (heuristic) law, would that still be a problem in
> another 5 years?
If it increases as exponential function of N, and N itself
naturally grows exponentially, you betcha!
If you started with N=10 employees, and the best computer you could
afford could just barely handle them, what with the ten-thousand
pages of tax code your software must obey, then over 18 months your
company grew to N=100, which forced you to wait one year before you
could afford a new computer able to process it entirely during one
pay-period (typically 1 week, 2 weeks, or one month), but since one
year is less than 18 months you're OK, you got the new computer six
months before you really needed its full capacity. But then over
the next 18 months your company grew to N=1000 employees, so now
you'll need to wait 10 years before you can afford a computer to
handle them, which is too late because you already needed this new
computer just two years after you bought the previous computer.
Since your company is growing exponentially, twice as many
employees every 18 months, a typical growth rate for a
well-concepted start-up, this means that every 18 months you'll be
waiting twice as long for the new computer you need *BY*PAYDAY*. So
eventually with longer and longer delays before you can get a new
computer you'll need for *regular* pay-days, you won't be able to
get that new computer in time to pay your employees on payday, so
then your employees get fed up and quit.
Whether your company doubles in 18 months or 6 months or 2 years,
eventually exponential cost function of number of employees,
applied to exponential growth in number of employees will beat
Moore's law which is *only* single exponential per time.
Why would payroll cost o(exp(NumEmployees))? Maybe the union
contract requires you run a traveling salesman algorithm to find
the optimum (least total travel) way for a linear (bucket brigade)
e-mail e-payroll system to pay everyone. Or maybe paycheques are
handed out at a party, and seating has to be arranged, which
requires all possible permutations and groupings of seating to be
considered, with the least-antagonistic seating arrangement to be
chosen, so as to minimize the number of quarrels for which your
insurance plan must pay medical expenses and damages to avoid an
even more costly lawsuit. It doesn't matter. The point is that
dismissing big-O estimates with "Moore's Law will save me" is
short-sighted, literally, it works in the short run but not in the
long run as N increases beyond some threshold.
Ben Bacarisse
> On Aug 31, 1:27 pm, arnuld <sunr...@invalid.address> wrote:
>> If T(n) = (n+1)^2 , how it can be deduced
>> that it is T(n) = O(n^2). n^2 is never equal to (n+1)^2
>
> What is the ratio between n^2 and (n+1)^2 when n is really big?
>
> The ratio is about 1, right?
>
> Say for example n = 1,000,000
>
> Then n^2 = 1,000,000 ^ 2 = 1,000,000,000,000
>
> And (n+1)^2 = (1,000,000 + 1) ^ 2
> = 1,000,001 ^ 2 = 1,000,002,000,001
>
> So the ratio is:
> 1,000,002,000,001 / 1,000,000,000
> = 1.000002000001
>
> Pretty darn close to 1. In fact as n gets larger and larger, the
> ratio gets closer and closer to 1.
>
> So if we are only interested in the expression when n is large, we can
> simplify (n+1)^2 and just call it about n^2. It's easier to think
> about.
>
> That is all this "big O" notation is saying.
>
> "f(n) = O(g(n))" just means that when n is large, the ratio between f
> and g is about constant.
That's a nice explanation but it has a small flaw -- it's not correct!
It is correct for the kind of functions that one usually encounters in
the analysis of algorithms so it is not as wrong as it would be in a
maths class, but I'd still want to make sure that a student knew what
the notation really means.
> We usually don't need to calculate the time performance of an
> algorithm to the millisecond. Usually we just need ballpark figures.
> The study of "big O" notation gives us a tool to calculate those
> ballpark figures quicker than calculating the exact ones.
This is more peculiar. I don't see how a notation that ignores so
much can help you calculate anything of any practical value.
> That should provide sufficient motivation to understand *why* we are
> studying this.
The notation helps you classify algorithms by putting them into
classes based on resource usage. That is how I would motivate the
notation.
<snip>
--
Ben.
Andrew Tomazos
I'm assuming the domain and range of the functions are the positive
reals and they are continuous and strictly increasing. Is that what
you are referring to? It wasn't intended as a rigorous definition,
just trying to provoke the OP's intuition.
> > We usually don't need to calculate the time performance of an
> > algorithm to the millisecond. Usually we just need ballpark figures.
> > The study of "big O" notation gives us a tool to calculate those
> > ballpark figures quicker than calculating the exact ones.
>
> This is more peculiar. I don't see how a notation that ignores so
> much can help you calculate anything of any practical value.
When n is large, an asympototically equivalent expression usually
gives a ballpark estimate. If I want to calculate (n+1)^2 for large
n, I can just calculate n^2 instead. Yes, it can be out by a
constant factor, and that constant factor can technically be anything,
but usually it's not large. It is usually at a minimum fine-grained
enough to give the difference between nanoseconds, hours, months and
until the sun burns out. :)
> > That should provide sufficient motivation to understand *why* we are
> > studying this.
>
> The notation helps you classify algorithms by putting them into
> classes based on resource usage. That is how I would motivate the
> notation.
Of what practical application are these "resource usage classes" if I
can't create some sort of estimate of how much resources a particular
algorithm would use?
-Andrew.
Ben Bacarisse
Yes.
> It wasn't intended as a rigorous definition,
> just trying to provoke the OP's intuition.
>
>> > We usually don't need to calculate the time performance of an
>> > algorithm to the millisecond. Usually we just need ballpark figures.
>> > The study of "big O" notation gives us a tool to calculate those
>> > ballpark figures quicker than calculating the exact ones.
>>
>> This is more peculiar. I don't see how a notation that ignores so
>> much can help you calculate anything of any practical value.
>
> When n is large, an asympototically equivalent expression usually
> gives a ballpark estimate. If I want to calculate (n+1)^2 for large
> n, I can just calculate n^2 instead. Yes, it can be out by a
> constant factor, and that constant factor can technically be anything,
> but usually it's not large. It is usually at a minimum fine-grained
> enough to give the difference between nanoseconds, hours, months and
> until the sun burns out. :)
This is true of the functions but not of the classes of function
describes by the big O notation. You can do a ball-park comparison
between f(n) = n log n and g(n) = n^2 but not between O(f) and O(g).
There are functions in O(g) that are bounded above by functions in
O(f) for all practical inputs.
Now, I know you know this. My point is that to say '"big O" notation
gives us a tool to calculate those ballpark figures' confuses what it
about. The functions themselves give us the tool to do this ballpark
calculation, the big O class tells us something quite abstract about
the nature of the algorithm.
Experienced people switch between the formal meaning and the practical
significance with ease because they have understood[1] the subtle
distinctions involved, but when someone is learning what the concept
is, some descriptions can lead the learner very far astray. Using big
O to calculate something seem like one of these dangerous memes.
>> > That should provide sufficient motivation to understand *why* we are
>> > studying this.
>>
>> The notation helps you classify algorithms by putting them into
>> classes based on resource usage. That is how I would motivate the
>> notation.
>
> Of what practical application are these "resource usage classes" if I
> can't create some sort of estimate of how much resources a particular
> algorithm would use?
That is one of the questions I would like a student to be able to
answer after a course on this material. If they answered "because big
O notation lets you calculate a ball-park running time" I'd think they
have some way to go yet. I'd prefer something like "it lets you
compare algorithms at a higher level of abstraction than you can
without it", though a whole essay could be written on the topic.
--
Ben.