Question

Find the best case, worst case and average case complexity for numbers of comparison and assignment operations for the following code. Indicate when there is no best or worst case. Comparisons Assignments Given 2-D array of integer map[n][n]: Best: Best: worst: worst: for (i0; 1 <n; i++) for(j = 0j <n; j++) If (map 10] < 0) map[001-mapli01: average: average: For ease of analysis, assume half of the elements in map are negative.

Answer 1

ANS:

Comparison:

   map[i][j]<0

it will run for every value of i,j;

So, it will run (n * n) times.Means O(n2).

it's complexity is equal in all the cases.

BEST: O(n2);

WORST: O(n2);

AVERAGE: O(n2);

assignment:

map[i][j]=-map[i][j];

it will run when the condition become true.

So, when map[i][j] is less than 0; then assignment will run.

BEST: if all the value of map[i][j] >=0;then the assignment will not run any time.

time complexity =O(1)

AVERAGE: if half of the value of map[i][j] is less than 0; then assignment will run (n * n) / 2 time;

time complexity = O([n* n]/2)=O(n2).

WORST: if all the value of map[i][j] is less than 0 , then assignment will run (n * n) times (i.e O(n2)).

time comlexity=O(n2).