Question

Analysing Algorithmic Efficiency (Marks: 3)

Analyze the following code fragment and provide an asymptotic (Θ) bound on the running time as a function of n. You do not need to give a formal proof, but you should justify your answer.

1: foo ← 0

2: for i ← 0 to 2n ² do

3: foo ← foo × 4

4: for j ← 1396 to 2020 do

5: for k ← 4i to 6i do

6: foo ← foo × k

7: end for

8: end for

9: end for

Answer 1

ANSWER :

Now in this question, you need to know about loop unrolling.

Which means, you should try to take pen and paper, chck what are the values, loop can produce.

Now lets analyse the first loop.

It goes from 0 to 2n*n, that means outer loop gives us, O(N*N) Complexity

LOOP 2

It goes from 1396 to 2020,

Now this is the constant time, the loop goes for each value of i

NOTE : any loop which is not dependent on N or input size is considered as, constant

So TO for this loop O(1)

LOOP 3

This loop goes from 4i to 6i

Lets check it in another way,

4* 2*n*n to 6*2*n*n as, i=2*n*n

Now take, 2*n*n common

It makes, 2*n*n (4 to 6)

Thus you can see, TO for this loop is O(n*n)

So finally for each i, internal loops goes for n*n

So, i goes for n*n, thus totally TO becomes

O(n*n*n*n)

NOTE : i would suggest to check out some good techniques to unroll loops from geeksforgeeks site.

HAPPY Learning!

( PLEASE VOTE FOR THIS ANSWER )

I THINK IT WILL BE USEFULL TO YOU .....

PLZZZZ COMMENT IF YOU HAVE ANY PROBLEM I WILL TRY TO SOVLE IT ........

THANK YOU .....