for x=1 to n

for y=1 to n/2

for z=1 to n/3

a=a+x*y*z

(i) Derive and justify its time complexity using Big-O notation

(ii) You have been given the following execution times for a program which implements this algorithm. The program has two parts. The first is constant and independent of n a fixed overhead, the second implements the algorithm above.

N 250 500

Execution time 110 msec 180 msec

Estimate and justify how long it would take to execute for n=1000