Importance of Big O notation

September 2, 2009 at 10:27 am | Posted in Hacking, Programming | Leave a comment
Tags: , , , , , ,

From a longer time I used to think that Big O notation O(n) , isn’t really much practical. I was reading section 1.4 of Data Structures and Algorithms by Aho, Hocraft and Ullman and was unable to understand how big O notation was being discussed. I asked for help on comp.programming and saw not many people agree with me. I hope this discussion will help you broaden your programming skills

Here is the relevant discussion. It is not the full discussion, it is filtered. I have posted here only those replies the ones I trust. Any posts, that I don’t trust or I have no idea about whether to trust them or not, are not included:

Original Question by me:

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.

Replies:

> 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__

—————————————————————-

> 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.


Richard Heathfield
Email: -http://www. +rjh@
“Usenet is a strange place” – dmr 29 July 1999
Sig line vacant – apply within

—————————————————————-

>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

 

 


Copyright © 2006, 2007, 2008 Arnuld Uttre, #331/type-2/sector-1, Naya Nangal, Distt. – Ropar, Punjab (INDIA) – 140126

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.

Advertisements

Leave a Comment »

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: