Time complexity algorithm


#1

Algorithm A and B spends exactly TA(n)=cAnlog2n and TB(n)=cBn^2 microseconds respectively .for a problem of size n find the best algorithm for processing n=2^20 data items if algorithm A spends 10 microseconds to process 1024 items and algorithm B spends only 1 microsecond to process 1024 items?


#2

The constant factors for A and B are

CA=10/1024* log2*1024
=1/1024

CB=1/1024^2

for processing 2^20=1024^2 items the algorithms A and B will speed
TA(2^20)=1/1024*2^log2(2^20)=2028 microseconds and
TB(2^20)=1/1024^2 *2^40=2^20 microseconds
because TB(2^20)>>TA(2^20),
the method of choice is A