Question

Discuss the best case, worst case, average case, time complexity and space complexity of an algorithm. Justify your answer with example​

Answer 1

Answer:

Complexity of an algorithm is analyzed in two perspectives: Time and Space.

Time Complexity:

• It is the amount of time required to run an algorithm in terms of the size of the input.

Space Complexity:

• Amount of memory an algorithm takes in terms of the size of input to the algorithm.
• Space complexity is sometimes ignored.

Linear Search

A[] = {8, 6, 12, 5, 9, 7, 4, 3, 16, 18}

Best case:

• Searching key element present at first index
• Best case time = 1
• B(n) = 1
• B(n) = O(1)

Worst case:

• Searching a key at last index or does not exist
• Worst case time = n
• W(n) = n
• W(n) = O(n)

Average case:

• If the key element is somewhere in the middle of the array.
• All possible case time / No. of cases
• Avg time = (1 + 2 + 3 + ... + n) / n = $\frac{\frac{n(n+1)}{2} }{n}$ = (n+1) / 2
• A(n) = O(n+1/2) = O(n)