@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 )
If you want to know how you can join us and get 100% Discount on your FEE ask Cyberian in Chat Room!
