Big O notation algorithms — OZONE Asylum, home of the Mad Scientists

OZONE

Big O notation algorithms

This page's ID: 28677

Edit Post

Who can edit a post?	The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.

Your User Name:
Your Password:
Login Options:	Remember Me On This Computer

Your Text: Insert Slimies » Insert UBB Code » Close Last Tag \| All Tags UBB Help	This is a little late, but... Your topic mentions "Big O notation," yet your post doesn't. This scares me a little because I don't think you realize the difference between "O(expression)" and just "expression". I assume the question you meant to ask was this: [i]Suppose algorithm A requires O(nlog2n) to sort n items and B requires O((n^2)/4) to sort the n items. For which n is algorithm B superior to algorithm A?[/i] There is no answer to this question. The reason is that Big-O-notation describes the runtime of an algorithm only as a proportion relative to itself. For instance, saying that an algorithm is O(n) only says that when you make n, say, twice as large, the algorithm takes twice the time to run. This could mean that the algorithm goes from 1 second to 2 seconds, or from 1 year to 2 years - there's no way to know from just the O(n). So, you know something about algorithm A, and you know something about algorithm B, but you don't know anything about them relative to each other. You don't know for specifically which n A is faster than B; you can only say that as n gets bigger and bigger, algorithm A will "eventually" be faster than algorithm B, because its runtime doesn't increase as quickly relative to n. This might happen when n is 10 or when n is 1000000. Your second question also worries me, because I'm worried that you're actually talking about big-O-notation as compared to big-Omega and big-Theta notation. The relationships between these notations can be compared to simple inequalities, but because of the subtleties I pointed out above, they are not equivalent! Perhaps you meant: [i]Show that n is Omega( 4(n/4)log(n/2) ) and that 4(n/4)log(n/2) is Theta( (n/4)log n ) [/i] In order to prove these, you will need to use the actual definitions of the notations. Specifically, to show that n is Omega( 4(n/4)log(n/2) ), you need to show that there are some values of n0 and M for which, when n > n0, n > M * 4(n/4)log(n/2). This is a little complex and may take some time to fully understand. Again, this is probably too late to help you with whatever assignment you were working on, but hopefully you'll find the actual knowledge useful... Loading...
Options:	Enable Slimies Enable Linkwords

« Backwards — Onwards »

Show Forum Drop Down Menu