## Importance of Big O notation

September 2, 2009 at 10:27 am | Posted in Hacking, Programming | Leave a commentTags: aho, algorithms, bog O notation, data structures, hopcraft, Programming, ullman

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?*

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

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

## Leave a Comment »

Create a free website or blog at WordPress.com.

Entries and comments feeds.

## Leave a Reply