Question

What is the f(n) runtime of the following pseudocode: sum-0 for A = N/2 downto 1 for B-1 t increment sum by B Explain: exactly what is wrong with the following diagram why it is incorrect how to fix it NP NP- Complete

Answer 1

The diagram part of the question is incomplete but the mathematical part has been solved below for you . However when the diagram will be attached it will be answered too.

Answer:

Following is the solution for the Time complexity/ Run Time:

Given that:

A = N/2 to 1

B = 1 to 4N

By summation:

Time Complexity = Lower bound of A * Upper Bound of B

Time Complexity = (N/2) * (4N)

By simplifying:

Time Complexity = N * 2N

Time Complexity = 2N^2

Hence the runtime f(n) for given pseudocode will be 2N^2

i hope it will help you!