Analyze the worst-case time complexity of the following algorithm using big- not

Question

Analyze the worst-case time complexity of the following algorithm using big- notation. Consider comparison as the basic operation. Algorithm 1 An algorithm to remove all duplicated integers in a list. procedure REMOVEDUPLICATE(A) A = (a_1, a_2,.. ., a_n: n unsorted integers, n greaterthanorequalto 1) S = {} Initialize S as an empty set B = an array of n Boolean variables for I left arrow 1, n do Initialize all B[i] to true B[i] = true end for for i left arrow 1, n -1 do Go through all numbers from a_1 to a_n-1 if B[i] = true then S = S union {a_i} Add a_i into set S for j left arrow I + 1, n do Go through all numbers from a_i+1 to a_n if a_i = a_j, then B[j] = false end if end for end if end for return S Return a list of integers with no duplicates end procedure

Explanation / Answer

In the Above Algorithm 3 For loop Used and in the Worst Case Each Loop Run n time.

So the Time Complexity will be O(n^3) in Worst Case If we consider compare as Basic operation.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---