Slideshow

Monday 25 February 2013


How do you calculate the complexity of sorting algorithms? Find the complexity
of Insertion sort and Bubble Sort. 

Ans:
The complexity of sorting algorithms depends on the input: sorting a thousand
numbers takes longer than sorting three numbers. The best notion of input size
depends on the problem being studied. For sorting algorithms, the most natural
measure is the number of items in the input that is array size n. We start by
associating time “cost” of each statement and the number of times each statement is
executed assuming that comments are not executable statements, and so do not take
any time.
Complexity of Bubble sort: O(n2)
Complexity of Insertion sort: O(n2)

No comments:

Post a Comment