In the following segment of code void say hello int n for in

In the following segment of code, void say hello (int n) {for (int i = 1; i

Solution

void say_hello(int n){

for(int i=1;i<=n;i++){ runs times

for(int j=i;j<=n;j++){ runs i times for each (n-i+1) times

puts(\"hello\"); runs constant time

}

}

}

a) when i =1 inner loop runs runs n times

when i =2 inner loop runs runs n-1 times

....

when i =n inner loop runs runs 1 times

hence total complexity = n+(n-1)+(n-2)+...+1=n(n+1)/2

b) T(n) = 1/2(n^2+n)

as n grows larger n can be neglected compared to n^2

hence T(n) = O(n^2)