Wednesday, 11 September 2013

Exercise (Big-Oh): How do find intersection of two functions where n = 100 for example

Exercise (Big-Oh): How do find intersection of two functions where n = 100
for example

I am trying to understand how n^2 is faster than nlogn for n < 100 and
opposite when n >= 100. In general this is not the case but this is an
exercise that I do not want an answer for but to lead me to the right
direction. I can picture two function in a graph that intersection at n =
100 as n < 100 O(n^2) is faster and as n > 100 O(nlogn) is faster.
I came up with an^2+b and c*nlog(n)+d
The key to my understanding here is constant that makes the differences.
But what is hard is that I need to come up with constants that will
satisfy the above scenario. Is there a way or technique that is done or am
I going correctly on the wrong direction?
Original question: James and Brad are arguing about the performance of
their sorting algorithms. James claims that hisO(N logN)-time algorithm is
always faster than Brad's O(N2)-time algorithm. To settle the issue, they
implement and run the two algorithms on many randomly generated data sets.
To James' dismay, they find that if N < 100 the O(N2)-time algorithm
actually runs faster, and only when&#8232;N >= 100 the O(N logN)-time one
is better. Explain why the above scenario is possible. You may give
numerical examples.

No comments:

Post a Comment