3 ms·

A Gentle Introduction to Algorithm Complexity Analysis (2012)

91 points by epenn 12y ago

men 12y ago
Very nice resource to have in mind. Thanks. I just started reading SICP. Decided to take a short detour to get a better grasp on all this complexity stuff that's hardly elaborated in SICP. Right now I am working through the chapter on Algorithm Efficiency Analysis in Discrete Math and Applications by Susanna Epp.
tlarkworthy 12y ago
A handy tip to reverse engineer complexity from empirical examples is plot on a log-log plot and measure the gradient (if its a straight line). The gradient is the exponent, ie. O(n^gradient). Great if your algorithm is so complex you can't analyze it. http://www.dgp.toronto.edu/people/JamesStewart/378notes/05logLog/ http://www.dgp.toronto.edu/people/JamesStewart/378notes/05lo...
- copperx 12y ago
  Isn't this the same as the power law?
mholt 12y ago
Well, I appreciate that the article is easier to read than most textbooks on the subject. (But for as long as it is, it really is just an introduction - scrapes the surface.) Also, what's up with the random pictures in the comments?
muyuu 12y ago
What's with the pics in the comments? I'm a bit confused. Is this something about that site?
- sleazebreeze 12y ago
  FTA: Thanks for reading. I didn't get paid to write this article, so if you liked it, send me an e-mail to say hello. I enjoy receiving pictures of places around the world, so feel free to attach a picture of yourself in your city!
shobhitverma 12y ago
Which problem is more important a) Make simple algorithms more accessible to the masses who do not get it even after reading a book. OR b) Make more complex algorithms and programming patters/styles more accessible to the good programmers who want to become excellent programmers ? I would like your opinion and how you define "importance" ( it could be market size, or economic impact in the world, or as some people have argued -- reduces gender inequality in tech)

3 ms·

A Gentle Introduction to Algorithm Complexity Analysis (2012)

91 points by epenn 12y ago

men 12y ago
Very nice resource to have in mind. Thanks. I just started reading SICP. Decided to take a short detour to get a better grasp on all this complexity stuff that's hardly elaborated in SICP. Right now I am working through the chapter on Algorithm Efficiency Analysis in Discrete Math and Applications by Susanna Epp.
tlarkworthy 12y ago
A handy tip to reverse engineer complexity from empirical examples is plot on a log-log plot and measure the gradient (if its a straight line). The gradient is the exponent, ie. O(n^gradient). Great if your algorithm is so complex you can't analyze it. http://www.dgp.toronto.edu/people/JamesStewart/378notes/05logLog/ http://www.dgp.toronto.edu/people/JamesStewart/378notes/05lo...
- copperx 12y ago
  Isn't this the same as the power law?
mholt 12y ago
Well, I appreciate that the article is easier to read than most textbooks on the subject. (But for as long as it is, it really is just an introduction - scrapes the surface.) Also, what's up with the random pictures in the comments?
muyuu 12y ago
What's with the pics in the comments? I'm a bit confused. Is this something about that site?
- sleazebreeze 12y ago
  FTA: Thanks for reading. I didn't get paid to write this article, so if you liked it, send me an e-mail to say hello. I enjoy receiving pictures of places around the world, so feel free to attach a picture of yourself in your city!
shobhitverma 12y ago
Which problem is more important a) Make simple algorithms more accessible to the masses who do not get it even after reading a book. OR b) Make more complex algorithms and programming patters/styles more accessible to the good programmers who want to become excellent programmers ? I would like your opinion and how you define "importance" ( it could be market size, or economic impact in the world, or as some people have argued -- reduces gender inequality in tech)