Time complexity for T(N)=2T(N/2) + long n

[joaopaulo90]

Hi guys,

I am stuck calculating the time complexity of the recursion: T(N)=2T(N/2) + long n.
Any idea?

Thanks a lot

[BioPhysEngr]

Some questions that might help you reason your way through this:

(1) For a given N, how many times does it perform a recursive call (that is, how many times is T(n) calculated)?

(2) How much time is required per calculation of T(n) (if you assume the call to T(n/2) is immediately available instantly)?

Do you see how to combine the answers to these questions into a final answer?

[ceplm]

Haoloo asa ceva nu cred
deci vere:

T(N) = 2 * T(N/2) + n

if (n != N) => n is a constant -> time complexity is O(logN)

else if (n == N) :

T(N) = 2 * T(N / 2) + N
2 * T(N / 2) = 4 * T(N / 4) + N
4 * T(N / 4) = 8 * T(N / 8) + N
........................
something = 1 + N

2^k = N => k = log N k times
this means that we have k ecuations => T(N) = (N + N + ... + N) = O(NlogN) (eg: mergesort or quicksort if the pivot is chosen magicaly by Nicolae Guta Des Maimuta )

sunteti praf zau ))
bio ala nare scop in viata, e pe langa toatal

pana si astia stie mai bine mancatias http://www.trilulilu.ro/lautaruno1/dbedd6c73b7bfc