Question

I need help with my discrete math problem. can you show me step by step process . Thanks in advance

3. Give a big-O estimate and a pair of witnesses for the number additions used in this segment of an algorithm. t:= 0 for i:=1 ton for j := 1 to n-i t:=t+i+j

Answer 1

In case of any queries, please revert back.

We need to find Big-O estimate. These type of questions are solved by looking at 1 loop at 1 time.

1. The first loop runs a total of n times.

2. The second loop runs n-i times. This means :-

So, our desired statement runs :- n-1,n-2,n-3..... 1.

So, we need to sum this :-

This convereges to 1 in n-1 steps => (n-1)(n)/2 . So this is O(n^2).

Number of additions is (n-1)(n)/2.