6 ms·

A Gentle Introduction to Algorithm Complexity Analysis

132 points by gtklocker 14y ago

rlu 14y ago
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 >_>
- zaptheimpaler 14y 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.
  - rlu 14y ago
    Fair enough
  - wollw 14y 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.
    - dionyziz 14y ago
      CLRS has an exceptional introduction to complexity and in fact is an exceptional book on its whole. However, it is not always easy to follow for high school students who don't have a mathematical background, as it tends to get a bit formal. It's the same reason many programmers find it repulsive and wouldn't read past the first few pages. For example, the proof for the Master Theorem is clearly not that easy to follow. That's exactly the reason I wrote this article so that it's complete yet approachable to people without a mathematical background.
      - yuushi 14y ago
        That being said, the section containing the proof is starred if I remember. I imagine most people, even those reading CLRS, skip over it.
captaincrunch 14y ago
A gentle intro? It's a bloody novel!
- ucho 14y 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 :)
ssurowiec 14y ago
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 http://www.amazon.com/dp/1849967202
- kruk 14y 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 http://www.amazon.com/dp/0262033844
mbenjaminsmith 14y ago
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]
- Qworg 14y 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.
  - mbenjaminsmith 14y 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?
    - leif 14y ago
      In terms of just the expression, yes, you just count the largest term. In cases where you count more closely, it's either in the constant (quicksort vs mergesort) or in terms of removing randomness or amortization.
    - kruk 14y ago
      Yes, there are cases where the "insignificant" part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling. While the "insignificant" part would usually have to be really large to influence the running time, it's often the case that one algorithm is faster than another due to the second one having a large constant multiplier, even though the Big O notation would suggest otherwise (e.g. O(10nlogn) would be faster than O(1000*n)) It's also common that even if one of the algorithms is slower in the worst case scenario, its average case performance is better than asymptotically better solutions. A popular example of such might be the quicksort algorithm, which has the worst-case running time O(n^2) but in practice is usually faster than most O(nlogn) sorting algorithms.
tsurantino 14y 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.
sodelate 14y ago
similar topic in many Computer Algorithm Books

132 points by gtklocker 14y ago

rlu 14y ago

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

zaptheimpaler 14y 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.
- rlu 14y ago
  Fair enough
- wollw 14y 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.
  - dionyziz 14y ago
    CLRS has an exceptional introduction to complexity and in fact is an exceptional book on its whole. However, it is not always easy to follow for high school students who don't have a mathematical background, as it tends to get a bit formal. It's the same reason many programmers find it repulsive and wouldn't read past the first few pages. For example, the proof for the Master Theorem is clearly not that easy to follow. That's exactly the reason I wrote this article so that it's complete yet approachable to people without a mathematical background.
    - yuushi 14y ago
      That being said, the section containing the proof is starred if I remember. I imagine most people, even those reading CLRS, skip over it.

captaincrunch 14y ago

A gentle intro? It's a bloody novel!

ucho 14y 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 :)

ssurowiec 14y ago

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 http://www.amazon.com/dp/1849967202

kruk 14y 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 http://www.amazon.com/dp/0262033844

mbenjaminsmith 14y ago

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]

Qworg 14y 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.
- mbenjaminsmith 14y 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?
  - leif 14y ago
    In terms of just the expression, yes, you just count the largest term. In cases where you count more closely, it's either in the constant (quicksort vs mergesort) or in terms of removing randomness or amortization.
  - kruk 14y ago
    Yes, there are cases where the "insignificant" part is so significant it's actually more efficient to use asymptotically slower algorithm for everyday problem sizes. The Big O notation is not so much about running speed but about scaling. While the "insignificant" part would usually have to be really large to influence the running time, it's often the case that one algorithm is faster than another due to the second one having a large constant multiplier, even though the Big O notation would suggest otherwise (e.g. O(10nlogn) would be faster than O(1000*n)) It's also common that even if one of the algorithms is slower in the worst case scenario, its average case performance is better than asymptotically better solutions. A popular example of such might be the quicksort algorithm, which has the worst-case running time O(n^2) but in practice is usually faster than most O(nlogn) sorting algorithms.

tsurantino 14y 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.

sodelate 14y ago

similar topic in many Computer Algorithm Books