Find the Big-O of each of the two sorting algorithms. Algorithm first(list) loop

Question

Find the Big-O of each of the two sorting algorithms.

Algorithm first(list)
loop i = 0 to list.length
minIndex = i
loop j = i+1 to list.length
if list[j] < list[minIndex])
minIndex = j
swap(list[minIndex], list[i])

Algorithm second(list)
loop i = list.length to i>1 decrement i
maxIndex = 0
loop j = 1 to n
if list[j] > list[maxIndex]
maxIndex = j
if maxIndex == i - 1
start = 0
while (start < maxIndex)
swap(list[start],list[maxIndex])
start++
maxIndex--
start = 0
while (start < i-1)
swap(list[start],list[i])
start++
i--

Explanation / Answer

1. Algorithm first(list)

loop i = 0 to list.length

minIndex = i

loop j = i+1 to list.length

if list[j] < list[minIndex])

minIndex = j

swap(list[minIndex], list[i])

The above algorithm sorting the list in ascending order.

we are using nested loops and for each element that is 'i' j loop will repeat the loop from 'i+1' to 'list.length'

Assume there are 'n' elements in the list

Hence i loop will repeat n times and for each ith ,j loop will repeat

Hence time complexity directly proportinal to number of elements in the list.

i loop will take n times and j takes n times hence time complexity is Big-O(n^2).

2.Algorithm second(list)

loop i = list.length to i>1 decrement i

maxIndex = 0

loop j = 1 to n

if list[j] > list[maxIndex]

maxIndex = j

if maxIndex == i - 1

start = 0

while (start < maxIndex)

swap(list[start],list[maxIndex])

start++

maxIndex--

start = 0

while (start < i-1)

swap(list[start],list[i])

start++

i--

Assume there are 'n' elements in the list.we are using nested loops,each loop takes n times.

hence time complexity is Big-O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.