Give the asymptotic big Oh complexity of the following algor

Give the asymptotic (big Oh) complexity of the following algorithm; show all the work you do. Algorithm Foo(A[], n) x leftarrow 0 for i leftarrow 0 to n-1 do for j leftarrow to n-1 do x leftarrow x+A[j] for k leftarrow 1 to n^2 do x leftarrow x+k*A[i]

Solution

Find the asymptotic (big O(h)) complexity of the fallowing algorithm..

Algorithm Foo (A [], n)

x<-0

for i<-0 to n-1 do

for j<-i to n-1 do

                x<-x+A[j]

for k<-1 to n*n do

           x<-x+k*A[i]

Solution: as we can see there are total three loop

(i)---for i<-0 to n-1 do this loop will be executed 0 to n-1 time so the time Complexity will be O(n) time

(ii)--- for j<-i to n-1 do this loop will be depend upon outer loop value i so loop will be started from i to n-1 time so the time Complexity will be O(n) time . But this is inner loop and for every i

The loop is stared from every new value of (i) and goes up to n-1 for every iteration, so the time complexity of this loop will be _i^n-1 _i^n-1j= O(n²)

(iii)….. for k<-1 to n*n this loop is started from 1 and executed up to n² time but this is also inner loop and for every iteration of (i) the loop is executed from 1 to n² so the time complexity of this loop is O(n²)

So we calculate the final tome complexity of the given algorithm is:

                       O(h)= _i^n-1(_i^n-1j + ₁^n*nk)=Select maximum(O(h)(O(h)+O(h)O(h))=n(n+n²)= n³

So the time complexity O(h)= O(n³)