• Create Account

orizvi

Member Since 05 Feb 2011
Offline Last Active Apr 11 2013 08:12 PM

In Topic: Confused on Big Oh

13 March 2013 - 03:40 PM

If anyone is interested in hearing what's wrong with that post, please ask and I will explain. Otherwise, I won't waste my time.

That's not a very useful response. If you have an objection to my post - please elaborate since otherwise we can't really discuss it. And that's the point of a forum, to discuss things - isn't it?

Or would you like me to guess why you disagree?

It isn't true that Big-O = worst case, Big-Omega = best case, and Big-Theta = average case.

Big-O = upper bound. We are often interested in an upper bound on the worst case so it gets associated with worst case behavior, but we are also often interested in an upper bound on  average case behavior, etc.

Hmm.. You're right - I should have used upper bound, lower bound etc instead of worst case, best case etc.

And on more complex algorithms with very complicated behaviour I can see how we'd want to consider the upper bound on the average behavior etc.

I'm still not entirely convinced that using Big-O in such a manner is the best approach, but at least the way you explained it seems mathematically sound.

In Topic: Confused on Big Oh

13 March 2013 - 02:53 PM

Quote

name='Wikipedia']
quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Right there, you see a use of big-O notation for the average case.

EDIT: And a bunch of examples in one place (a whole table, actually): http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Tragically you gave an example of incorrect usages of Big-O notation.

Big-O notation is only for worst case growth of a function. Please refer to the formal definition also provided on wikipedia or any number of math texts. (Formal definition on wikipedia as I can't link to math texts: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition)

Now - that doesn't mean that the Big-O for a particular function can't be the same as one or even all of the 5 Bachmann-Landu notations. Consider the very simple case of an algorithm that goes through a list of n numbers and adds 1 to each number. That would take n operations exactly - which means its worst case is n, its average case is n, and its best case is also n.

If you read the paragraph just above the table you mentioned the author states:

The run time and the memory of algorithms could be measured using various notations like theta, omega, Big-O, small-o, etc. The memory and the run times below are applicable for all the 5 notations.

Please see the following for an explanation of the other notations used: http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations

Outside of theoretical CS - you probably won't be seeing the other notations, as the common practice seems to be simply to abuse Big-O and use it everywhere even if it is an incorrect usage.

In Topic: Confused on Big Oh

12 March 2013 - 11:04 PM

I found the data structure I was actually thinking of, even though other people have offered lots of great examples too.

http://msdn.microsoft.com/en-ca/library/system.collections.specialized.hybriddictionary.aspx

See the remarks section of that class and the classes it links to. Offers lots of great insight.

Overall - every algorithm has its advantages and disadvantages - there are no super algorithms that are magically better, simply some that are better in solving certain problems.

In Topic: Confused on Big Oh

12 March 2013 - 06:15 PM

Expanding on frob's answer above. Refer to my previous post.

Big O notation is defining the upper bounds of the growth of a function

Its important to note the word "Growth" in there. So n^3 will grow to requiring more operations faster than n^2 - but without considering the C and k constants - it makes no guarantees about performance.

Essentially the way you should view the formulas is that when you substitute a value for n the result is the number of operations required.

So the more number of operations required = more time required but Big O doesn't provide us with details on how many operations are required since if you look back to how the proof for Big O is done - that information is lost in the process.

Lets say I have the following task: I have a binder of unsorted papers, and I want to find a particular paper. If I have n number of papers in the binder - in the worst case scenario I would perform n checks to see if it's the paper I want.

That would give me a function we can define as f(x) = n since I have to perform n checks, and it would also be O(n).

Now if for whatever reason - in addition to looking through the papers in the binder, I also had to perform a calculation or some other operation for every page (maybe now I need to perform two comparisons since there are two possible ways to match the page I want). My function would be f(x) = 2n, which intuitively makes sense as taking more time since we have to do twice as many comparisons.

Its important to note that this second function would also be O(n) since Big O notation isn't so much interested in comparing the exact number of operations between functions but rather their growth - which in the case of both functions is linear (or n). And this also illustrates the reason why the C and k constants are important since for the first example - C = 1, k = 0, for the second example C = 2, and k = 0.

I'd also like to mention that there are a whole set of notations like Big O which all have to be considered to do a proper comparison of algorithms. Big O gives us upper bound, but there's still the average, and lower bounds to consider... But most people generally only look at worst case/upper bound for a quick sanity check. See http://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer_science

In the real world - much of this doesn't really matter as frob mentioned. But as an example of  a real world example where it does matter is if you read through the implementation details of some generic data structures in the .Net Framework - they're actually implemented in such a way that depending on the number of items, they'll use different algorithms. This is because for small data sets (smaller values of n) an algorithm with a greater order of complexity actually performed better, but as the data set increases (for larger values of n) - a different algorithm is preferred because it has a lower order of complexity.

In Topic: Paying to enter a shop?

12 March 2013 - 05:01 PM

A tax to get into the City where the best and wealthiest merchants are as opposed to the Towns where its free to enter but the selection is smaller and worse.

PARTNERS