A Gentle Introduction to Algorithm Complexity Analysis (opens in new tab)

(discrete.gr)

132 pointsgtklocker13y ago23 comments

23 comments

13 comments · 6 top-level

rlu13y ago· 3 in thread

I wonder if the title is in jest. Clicking on this link and then being greeted with a wall of text (literally! It fills my entire screen) is hardly gentle.

I'm sure it's a good read just not right now >_>

zaptheimpaler13y ago

I'd say thats why it is gentle. Most CS books will compress that content into 2-3 pages and expect you to figure the rest out as you go. On the other hand, this article doesn't require you to take some time to think about it at all, its all right there.

wollw13y ago

The classic CLRS Algorithms book actually starts out with a five chapter "Foundations" part that goes over computational complexity in a good amount of detail. It goes over theta, big and small O, and big and small omega notations and their properties similarly to how this article seems to. It has an entire chapter on determining the computational complexity of recurrences and another on randomized algorithms. The five chapters together are about 130 pages and probably not what I would call gentle but I found it surprisingly approachable.

1 more reply

rlu13y ago

Fair enough

mbenjaminsmith13y ago· 2 in thread

Great article. I've understood the why and what of Big-O but never how to do the analysis.

I have a question for the informed however:

The article says that we only consider the fastest growing parts of an algorithm. So, counting instructions, n^2 + 2n would just be n^2. But why do we do that? Imagine an algorithm where we have n^12 + n^2 + n^2 + n^2 + n^2, etc. Do we really ignore each n^2 section?

[Edited]

Qworg13y ago

I assume you mean n^2 + 2n right?

Given your example, you ignore the n^2 because n^12 grows SO much faster. For any "normal" amount of operations, n^12 wipes out 4*n^2 in terms of cost.

mbenjaminsmith13y ago

Correct, I meant n^2.

Certainly there are cases where the "insignificant" parts of an algorithm are not so, correct? In a simple case n^12 dominates a few n^2 sections, but there must be exceptions to that.

Are there cases where a more complete analysis is done -- like comparing two similar algorithms? Or at that point are you actually implementing the algorithms to test and measure?

3 more replies

ssurowiec13y ago· 1 in thread

For anyone interested in this subject I'd highly recommend the Algorithm Design Manual by Steven Skiena[0]. He goes over this in pretty good detail in the first ~1/4 of the book. This was my first introduction to Algorithm Complexity Analysis and by the end of that section I already found myself looking at my code in a different light.

[0] http://www.amazon.com/dp/1849967202

kruk13y ago

I would recommend the Introduction to Algorithms by Cormen. It covers not only the complexity analysis but also describes the most important algorithms, data structures and classical problems solutions. http://www.amazon.com/dp/0262033844

captaincrunch13y ago· 1 in thread

A gentle intro? It's a bloody novel!

ucho13y ago

Nope, it is just an introduction. I would love to see next parts, my memory of Complexity Analysis is very rusty. Basically I only remember people _repeating_ that course, leaving the exam just after seeing questions :)

tsurantino13y ago

I've been doing the Coursera course on Algorithms (from Stanford by Tim Roughgarden). He's going over concepts like Big-O notation as well as analyzing algorithms. This particular article is a refreshing read, and I would highly suggest the Coursera course as an accompaniment if someone wants to go deeper.

sodelate13y ago

similar topic in many Computer Algorithm Books

j / k navigate · click thread line to collapse