Question

Provide a "big oh" run-time analysis for each of the following. When a value of “n” is used, it is the size of the input.

4.) void problem 40 cin n min max for (int i min i n, i++) for (int j- 1: j< max, j++) tota while (total n tota total 2 total 5.) void problem 50 cin n; for (int i 0: i n, i++) for (int j 0; j i2; j++) for (int k 0; k <j2; k++) sushi salmon tuna mackeral total

Answer 1

4) if you see there is nested loop

since the i loop goes from min to n
and j loop goes from 1 to max
so complexity is o(n * max)
and there is also whileloop after the nested loop which goes to n
so complexity is O(n)
so total complexity is O(n * max) +O(n) = O(n)

5)
There is 3 nested loop
i loop goes from 0 to n ==> complexity is O(n)
j loop goes from 0 to i² ==> since maximum value of i is n
so j loop goes to n² ==> so complexity is O(n²)

K loop goes from 0 to j² ==> since maximum value of j is n²
so k loop goes to n⁴ ==> so complexity is O(n⁴)

so total complexity is O(n * n² *n⁴ ) = O(n⁷)