Good text on order analysis

Question

As a self-taught computer programmer, I'm often at a loss to estimate the O() value for a particular operation. Yeah, I know off the top of my head most of the important ones, like for the major sorts and searches, but I don't know how to calculate one when something new comes along, unless it's blindingly obvious. Is there a good web site or text that explains how to do that? Heck, I don't even know what computer scientists call it, so I can't google it.

Answer 1

It's called Big O Notation, and it's used in Computational Complexity Theory.

The wikipedia articles are a pretty good starting point, as are the bibliography at the bottom of the page.

Answer 2

Introduction to Algorithms is the standard text used at most universities. I've used it and can recommend those chapters on order analysis. I'd start with the articles in Tim Howland's answer, though.

Answer 3

It is called algorithm analysis and is a science in itself. Take a look at some of the books here

Answer 4

If you really want to learn this topic, then you probably need a standard theory/algorithms textbook. I don't know of any website that can actually teach you complexity analysis ("complexity" or "time complexity" is how you call those O() values; you might also want to google for "analysis of algorithms" or "introduction to algorithms" or such).

But before that -- a free option. There are slides from a course given by Erik Demaine and Charles Leiserson in MIT, that are free and look great. I would definitely try to read them and see if that works for you. They are here.

Now, textbooks:

The classical choice for a textbook is Cormen et al's book Introduction to Algorithms (there might be a cheap version available to buy here and I remember seeing a free (possibly illegal) version online, but I don't remember where).

A more recent and modern-style book, which is IMO more fun to read and a better choice, is Kleinberg and Tardos' Algorithm Design.

Here are some websites with information (I got these by googling "algorithm analysis lecture notes" without the quotes):

• Algorithms Lecture Notes
• Lecture notes by Steve Skiena

The above is written by a computer science theorist. So programmers or other practical people might have some different opinions.

Answer 5

Your links takes me to a site in Russian that seems to want a userid and password. Legitimate mistake, or troll? Paul Tomblin

The site is in Bulgarian and you shouldn't need a password to access the list of files I linked to and download some of them. Unless of course there is an access restiction for IPs from outside Bulgaria, which I really don't know.

Sorry, I don't know how to make a comment.