Give the worse-case running time using Big-Oh notation for the following: 4. r=0 for i:=1 to n - 1 do forj:= i + 1 to n do return r for k:=1 toj do r:=r+1 Popping all of the elements off a stack and placing them in a linked list. Finding the smallest value in an unsorted array of integers
r=0
for i=1 to n-1 do : runs from i=1 to n-1 : possible values for i :1,2,3...,n-1
for j =i+1 to n do : runs from j=i+1 to n : possible values for j : 2 to n, 3 to n, 4 to n,...,n-1 to n
for k=1 to j do : runs for j times :
when i=1,j : 2 to n, this loop runs for :2+3+..+n
when i=2,j : 3 to n, this loop runs for :3+4+..+n
when i=3,j : 2 to n, this loop runs for :4+5+..+n
.
.
when i=n-2,j : n-1 to n, this loop runs for :n-1+n
Overall these loops runs for :(2+3+..+n) + (3+4+..+n) + (4+5+..+n) + ...+ (n-1+n) = 1*2+ 2*3 +3*4+4*5+...+n-1*n = which is summation of n*(n+1) = summation of n^2 +n = summation of n^2 + summation of n = n(n+1)(2n+1)/6 + n(n+1)/2 = n(n+1)(2n+4)/6
r=r+1
So, run time of this code is :n(n+1)(2n+4)/6 = O(n^3)
Step by step
Solved in 4 steps
