@zareen said in CS502 Assignment No. 02 Solution and Discussion:

You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 02.

ANS: C1 = (n-1) C2 = (n-1)+(n-2)+…+1 = C3 = (n-1) T(n) = (n-1) . C1 + . C2 + (n-1)C3 T(n) = an2 + bn + c Here a,b and c are constants in term of C1, C2 and C3 T(n) = O(n2)

@zareen said in CS502 Assignment No. 01 Solution and Discussion:

Question No 02: (Marks: 10)
You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 01.

Solution:
Question No. 02: The step by stem analysis of the algorithm designed in question 1 is as follow,

The time taken by each statement (step) is given as follows,

Step 1: C1 // Execute only 1 time or Constant Time or O (1)
Step 2: C2 // Execute only 1 time or Constant Time or O (1)
Step 3: n -2 // Execute n -2 times
Step 4: n -2 // Execute n -2 times
Step 5: n – 2 // Execute n -2 times
Step 6: C3 // Execute only 1 time or Constant Time or O (1)
Step 7: C4 // Execute only 1 time or Constant Time or O (1)
Step 8: C5 // Execute only 1 time or Constant Time or O (1)
Step 9: C6 // Execute only 1 time or Constant Time or O (1)

Total time T(n) can be calculated as follows,

T(n) = C1 + C2 + (n -2 ) + (n -2 ) + (n -2 ) + C3 + C4 + C5 + C6
T(n) = C1 + C2 + n -2 + n -2 + n -2 + C3 + C4 + C5 + C6
T(n) = C1 + C2 + n + n + n - 6 + C3 + C4 + C5 + C6
T(n) = 3n + C1 + C2 + C3 + C4 + C5 + C6 -6
T(n) = 3n + (C1 + C2 + C3 + C4 + C5 + C6 -6)
T(n) = 3n + C7 // C7 = (C1 + C2 + C3 + C4 + C5 + C6 -6)
T(n) = n // Ignoring constant terms

Or T(n) = O (n )