Hi all. I have this problem with analysis of algorithms, I thought maybe I could get some help here... It's not defined *that* strictly, so I guess I shouldn't be looking for an exact solution. This is how it goes:
---------------------------------------------------------------------------------------------------------------------- You have an algorithm "A" that solves a given problem in N/2 steps of complexity O(N^2) each, for an input set of size N. (exact kind of complexity is not stated) Suppose you come up with another algorithm "B" for the same problem, a "divide and conquer" one. This algorithm divides the input of size N in two pairs of size N/2 each. To achieve this subdivision it takes an amount of "data division operations" D(N) = O(N*logN) and an amount of "data combination operations" C(N) = O(N*logN) The problem is to determine which of the two algorithms is more efficient for this problem; A or B? ---------------------------------------------------------------------------------------------------------------------- Reasonably, I tried to find upper bounds for the number of "operations" needed in both cases and see which one comes up with a "tighter" bound. A: T(N) = (N/2)*f(N), where f(N) = O(N^2) Thus T(N) < (N/2)*(c1*N^2) = c2*N^3, where c1,c2 are constant. B: T(N) = 2*T(N/2) = 2*(D(N/2)+C(N/2)), therefore T(N) < 2*c3*(N/2)*log(N/2) = c4*N*(logN-log2), where c"?" are constant Is this enough to deem "B" as the more efficient one? Or am I missing/doing wrong something here? Is there a pitfall somewhere? and BTW, doesn't the recurrence "T(N) = 2T(N/2) + constant" yield linear complexity? How do I come up with N*log(N) ? Thanks in advance for any input. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
