0

What steps are required in determining the Big-Oh notation for the algorithm when sorting an array of integers 5 7 4 9 8 5 6 3 and showing the contents each time a selection sort changes it while sorting the array into ascending order and descending order? I need to do an evaluation of the Big-Oh notation before I come up with a Java program to sort the elements in ascending and descending order

codex3
  • 3
  • 1
  • 2
    https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/487278#487278 – The Scientific Method Oct 18 '18 at 18:46
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – aldr Oct 18 '18 at 21:42

1 Answers1

0

When finding the Big Oh for any algorithm, you must count the number of instructions that are performed in the algorithm, usually by finding a pattern for when they are performed. You must also consider the instructions that occur in the worst case (i.e. when searching a list, worst case is that visit every element). For selection sort, a simplified break down of the algorithm it that for a list of n elements, each element is compared the other elements in the list. The switching of elements and the printing of the n elements also occurs essentially for every element. Roughly this would look like this in code:

  • For every n element

    -Go through list and compare with every other element to the right of element

    -If the minimum element to right sub-array is less than the current element, switch

    -Print n elements in array.

So this will look like n*(n+1+n) which essentially is O(n^2) If your algorithm wants to do both ascending and descending, it doubles the n^2 which is still O(n^2)

Malia Latimer
  • 1