Algorithm and Data Structure

Question 1

Give time and space complexity of quick sort.

Answer 1

Best: omega( n logn )
Average: theta( n logn )
Worst: O( n^2 )

Question 2

Give time and space complexity of bubble sort.

Answer 2

Best: omega( n )
Average: theta( n^2 )
Worst: O( n^2 )

Question 3

Give time and space complexity of merge sort.

Answer 3

Best: omega( n logn )
Average: theta( n logn )
Worst: O( n logn )

Question 4

Give time and space complexity of insertion sort.

Answer 4

Best: omega( n )
Average: theta( n^2 )
Worst: O( n^2 )

Question 5

Give time and space complexity of selection sort.

Answer 5

Best: omega( n^2 )
Average: theta( n^2 )
Worst: O( n^2 )

Question 6

Give time and space complexity of heap sort.

Answer 6

Best: omega( n logn )
Average: theta( n logn )
Worst: O( n logn )

Question 7

Give time and space complexity of radix sort.

Answer 7

Best: omega( nk )
Average: theta( nk )
Worst: O( nk )

where k is the range of input values.

Question 8

Give time and space complexity of bucket sort.

Answer 8

Best: omega( n+k )
Average: theta( n+k )
Worst: O( n^2 )

where k is the range of input values.