Comments on C for Coding: Plain English Explanation of Big O Notation

I could not understand this concept in 4 years of ...

2011-01-14T11:49:20.094+08:00

I could not understand this concept in 4 years of college..I read this article and makes sense overnight.. Awesome article..Good Job and Thanks a million.

cheers !!! ...good one

2010-12-06T08:33:56.396+08:00

cheers !!! ...good one

please can some one tell me is there any function ...

2010-09-28T19:14:19.269+08:00

please can some one tell me is there any function for which Big O and Omega are same?? are there any fuctions exists?? for f(x) and g(x) for which both are same. Please mail me ansary_90@yahoo.com Thanks all

Great article, commendable efforts too... although...

2010-06-30T21:34:39.301+08:00

Great article, commendable efforts too... although your treatment of the concept is largely incomplete. Try effecting some of the corrections pointed out and give thorough dissection of all concepts in the original article.

Wow this was amazing - you should consider writing...

2010-06-14T17:55:08.717+08:00

Wow this was amazing - you should consider writing a book: Computer Science in PLAIN ENGLISH!

Thank you William! This is a very concise yet clea...

2010-05-03T10:34:03.928+08:00

Thank you William! This is a very concise yet clear explanation of Big-O and the other algorithm buzzwords.

Thanks for taking time to write this, I am sure many people will find this helpful.

Thanks William Shields! I just revisted your repl...

2010-02-22T15:01:43.138+08:00

Thanks William Shields! I just revisted your reply from 3 months ago and re-read the article. I understand now that that the O doesn't stand for anything, it just tells you that this is notation called Big-O. And the Big-O notation means not to take the notation literally, but as a concept to describe the complexity of a problem. So, for any number n, O(log n2) is more complex than O(log n) because there are more digits in the problem, thus increasing it's complexity. And the base of the log doesn't matter because there is a linear relationship among the base of logarithms that is insignificant when it comes to the complexity of the problem

similar to when you wrote "The astute may have realized that we could express the number of operations as: n2 + 2n. But as you saw from our example with two numbers of a million digits apiece, the second term (2n) becomes insignificant (accounting for 0.00002% of the total operations by that stage)."

The base portion is the insignificant portion (I think anyway).

Thanks for the "english" explanation!

Well its good explanation but i would like to know...

2010-01-27T03:54:59.442+08:00

Well its good explanation but i would like to know what does the Big-O actually do.I mean say we have 2 expressions O(n^2) and O(n^2logn)......how do we compare them and know which is better

"So the Big-O of the Travelling Salesman prob...

2010-01-17T19:14:56.020+08:00

"So the Big-O of the Travelling Salesman problem is O(n!) or factorial or combinatorial complexity."
I'm not clear what this means. Surely problems don't have complexities, only algorithms?

Also you give "Public Key Cryptography" is given as an algorithm of polynomial complexity. I thought it was unknown what the complexity of integer factorisation was.

Searching for a name in the telephone book (exampl...

2009-12-02T15:53:17.995+08:00

Searching for a name in the telephone book (example above) is a classic O(log n) algorithm.

1 name = 1 comparison
2-3 names = 2 comparisons
4-7 names = 3 comparisons
8-15 names = 4 comparisons
16-31 names = 5 comparisons
...
1,000,000 names = 21 comparisons

Logarithms are just the inverse of exponents ("to the power of").

2^20 = 1,048,576
log2 1,048,576 = 20

or

loga(a^n) = n

n in any O(...) expression is the meaningful quantifier and varies depending on the algorithm. For sorting it is typically the number of elements. For multiplication it is the number of digits.

Base isn't specified with O(log n). Whether it's log2 n, log10 n or log100 n is irrelevant just like it's irrelevant if its 2n, 10n or 100n. Mathematically there is a linear relationship between loga n and logb n.

Big O generally refers to expected or worst cases.

I'm a self taught programmer who's still h...

2009-12-02T15:31:39.809+08:00

I'm a self taught programmer who's still having some trouble with what O(log n) means. I understand logaritms (e.g. log base 2 1024 = 10), but what does the n mean in O(log n)? And what does the O mean. What is the base? 2? I think if the base is 2 then O means "the number of times you need to raise n to the power of 2 to get O?".

But I also think I'm totally wrong and I'm thinking too logically. Does O(log n) represent a concept as opposed to a formula? For instance does O(log n) mean that the worst case scenario is n times? and O(log n squared) mean the worst case scenario is n squared?

Please help!

That is an excellent article! I wish I'd read...

2009-10-06T10:40:49.909+08:00

That is an excellent article! I wish I'd read it yesterday, might not have screwed up my job interview this afternoon so badly :(

Thanks for writing it.

Great article! Could you go into more detail abou...

2009-09-19T05:47:35.948+08:00

Great article! Could you go into more detail about calculating the 'log'...

A very good explanation of Big O in plain english!...

2009-07-10T19:31:10.204+08:00

A very good explanation of Big O in plain english!

P.S: Been following your posts from a couple months now... "I'm lovin it" ;)

@Anonymous #3 - See Trey's comment: "unl...

2009-07-10T11:26:26.346+08:00

@Anonymous #3 -

See Trey's comment: "unlikely" in that section should read "likely". If you have the hashes of two files and the hashes are different, then the files are different. If the hashes are the same, then they're very likely the same - although they could be be different (by the Pigeonhole Principle) since people have been able to generate collisions (which is the link provided).

>> “you should do X because it’s O(2n) and Y is O(3n)”

This always pisses me off, since it's people who should know better (since they can presumably determine that an algorithm is O(2n)). Big-O, as you say, deals with the algorithm when the factor in question goes to infinity. In this case, the "2" vs. "3" isn't going to be an issue. Big-O is meant to compare the order of an algorithm's performance, as opposed to the details.

The rule of thumb, when I was taught Big-O, was to use 1000000000 for n - at which point it becomes apparent what the dominant factor is. Big-O isn't meant for comparing 2000000000 [O(2n)] to 3000000000 [O(3n)] - it's meant for comparing 2000000000 [O(2n)] to 1000000000000000000 [O(n^2)]. The other one we were taught is that O(n) is really O(kn), where k is a constant that we supress since it doesn't matter when making comparisons of this nature.

Excellent article. Thanks for taking the time :)

2009-07-10T10:47:25.783+08:00

Excellent article. Thanks for taking the time :)

>> If an algorithm is directly proportional ...

2009-07-10T06:00:05.237+08:00

>> If an algorithm is directly proportional to *the number of digits* in the problem size, then that algorithm has logarithmic complexity.

Put more accurately, the algorithm has logarithmic complexity relative to the size of the number. You are correct in this.

Unfortunately, computer scientists (largely) don't care about complexity relative to the size of the number. When dealing with numbers as input to a problem (as in the case of addition), computer scientists tend to care about complexity relative to the size of the *encoding* of the number (that is, its length when you write it down).

So: In a sense you're both right - Big Oh can be used to measure the complexity both ways. Normally, though, we talk about the one used in the article.

Also, one more explanation. In the function y = Ax...

2009-07-10T05:28:05.071+08:00

Also, one more explanation. In the function y = Ax , where A is a constant, y and x are "directly proportional". In the function y = log x , their relationship is logarithmic. So saying that an algorithm which is directly proprtional has logarithmic complexity is false.

@Anonymous commenter #2 >> If an algorithm ...

2009-07-10T05:21:29.433+08:00

@Anonymous commenter #2

>> If an algorithm is directly proportional to *the number of digits* in the problem size, then that algorithm has logarithmic complexity.

I am pretty sure the author was correct when he said that his human addition algorithm is linear complexity and that you are wrong when you say it is logarithmic. Logarithmic would mean having more digits in the numbers you are adding would yeild smaller changes in the number of operations required. How can you add two numbers without adding each digit? And why would the positive slope of the number of additions you need to make fall as the two numbers got bigger? Maybe you are confused about the details of the addition algorithm.

"Public Key Cryptography is a prime example.&...

2009-07-10T01:59:20.451+08:00

"Public Key Cryptography is a prime example."
pun intended? ;)

regarding the MD5 hash at the end of your post, yo...

2009-07-10T01:31:04.803+08:00

regarding the MD5 hash at the end of your post, you say:

" If they’re different, the files are different. If they’re the same, the files are highly unlikely to be the same."

Your saying that if the Hashes are the same then then they are *unlikely* to be the same as the full resolution file that generated the hash?

I can't quite grock that, could you have another go at explaining it, please?

If the hashes match and that means that they are unlikely to be the same as the originals, and if the hashes don't match you're saying that they are not the same too; so whats the point of hashes if they can't distinguish between same/non-same files?

I'm sure I'm missing something, its a great post thank you for writing it.

>> See the pattern? The complexity (being th...

2009-07-10T01:18:46.336+08:00

>> See the pattern? The complexity (being the number of operations) is directly proportional to the number of digits. We call this O(n) or linear complexity.

If an algorithm is directly proportional to *the number of digits* in the problem size, then that algorithm has logarithmic complexity.

An O(n) algorithm would be something like a linear search through the phone book, or a (very) naive primality test, but not simple addition.

You wrote "highly unlikely" when you mea...

2009-07-10T01:04:26.291+08:00

You wrote "highly unlikely" when you meant "highly likely".

Thanks William! This is by far the best explanatio...

2009-07-09T23:35:45.399+08:00

Thanks William! This is by far the best explanation of Big O in plain english.