Advertisement

Algorithm Analysis Document Review Requested

Started by November 16, 2018 08:49 PM
3 comments, last by Alberth 6 years, 3 months ago

Hello,

I've written (attached) a small, high level summary of the basics of algorithm analysis as a quick introduction or cheat sheet for some core concepts.  Could people who are skilled in this area please give constructive feedback on how to perhaps improve the document?  A review for accuracy of information presented and ideas for possibly expanding the document would be appreciated as well.  Please be gentle as this is my first attempt at something like this :)  Eventually, I'd be interested in publishing it or something similar. 

Thank you!

Algorithm Analysis – Quick Summary.pdf

Done > Perfect

The idea is there, but you're missing steps in your reasoning.

"number of lines" is a weird measure, many programs can be written in their entirety in a single line. We just tend not to format our code like that, as it is somewhat hard to read and edit ?

Take number of statements instead.

 

Your goal is to "quantify the number of lines", yet point 3 as well as the conclusion jumps to "worst case" running time. Also, you claim to want "number of lines", but point 3 speaks about "number of assignments"

In point 3 you also generalize to "n", without having that related to the program. This "n" also returns in the conclusion, where we suddenly have an "f(n)" out of nowhere. As for your formula, I think it's 1 + 2*(n-1), since the "if" and the assignment are 2 separate lines of code.

Tell the reader where you will be going, and don't change course along the way.

 

Section 2.3 starts with the conclusion about the example, rather than the general aim. What is the key information you want to get out of f(n) ?

I would say you want a (rough) estimate of the number of statements being executed, as the problem grows, ie n grows.

I think all your 3 simplifications are the same, fastest growing term wins. Not sure you should differentiate between the cases. On the other hand, it might be useful to show how it works for your examples.

 

At the end of 2.3 you throw in another surprise, "asymptotic analysis". No explanation at all what it is, or what you're trying to do with it there. Imagine it says "exositiain relevance avalanche" instead, and try to make sense of the sentence please.

(The point is, you know what it means, but to your audience, the term is a random sequence of English looking words, it has no meaning whatsoever to them until you explain it to them.)

2.4 is completely disconnected from the above text. "summary of common complexity examples", You never even mentioned "complexity" above. You also state "O(...)" without explanation what that means (that is, until after point 7).   Tell the reader where you're going before you take a walk with him. Introduce new concepts properly, explain the idea, how to read it, etc.

2.5 says it's about mathematical definitions, yet you throw in big-omega as a new concept, in about 5 lines of text.

Also, "f(n) < C_g(n) for all n > n_0" ? Is a programmer not aware of big-O supposed to understand that?

 

I think your article has a complexity of O(e**x), it starts very slow, and then turns on the rocket boosters, and hits theoretical math definitions in just 3 pages.

What exactly is your audience? What is their level of expertise?

 

The complicated part of writing is to think like your audience, instead of thinking like you. That is, act asif you are the audience, you have never heard of big-O, in fact, you have no clue that there is something like a scale problem, or that different algorithms scale differently. You would never have even dreamed someone made a notation for how stuff scales, or that you can discuss it in a generalized way.

What also helps a lot is to put the article down after you wrote it, leave it for a week or longer, and when you have sufficient time on your hands, play being a member of your audience again, and read it. Mark the occurrence of each new word. It is known knowledge, or is it explained right there?

If not, it's wrong.

Advertisement

Thank you VERY much for your in-depth reply.  This all makes sense and I'll be working on the suggestions you recommend!

Done > Perfect

One further thought, I think you also need to show how big-O is useful in practice. Your reader is a programmer, not a mathematician. The latter invent new higher level abstractions all day, big-O is just one of them.

If you don't show how big-O is useful ti your programmer audience, your article is just showing that mathematicians invented a complexity notion for algorithms. That's nice for mathematicians, but pretty useless to a programmer.

This topic is closed to new replies.

Advertisement