Question

#1. Using the definition of big-O, prove that f(x) = 5x^4+x^3+8x-2 . Show all work.

#2.

void bubbleSort(Student myClass[], int size) {
   int pass = 0;                            // counts each pass of the sort
   bool done = false;                       // whether sorted or not 

   // each pass puts one element into its sorted position,
   // smallest value bubbles to the top of the array
   while (!done) {
      done = true;                                 // possibly sorted

      // compare consecutive elements, swap if out of order
      for (int i = size-1; i > pass; i--) {
         if (myClass[i].id < myClass[i-1].id) {
            myswap(myClass[i], myClass[i-1]);
            done = false;                          // still not sorted
         }
      }
      pass++;
   }
}

Give an analysis of the running time (find a tight big-O) for the sort.

Give a brief written, more intuitive, explanation of the big-O answer.

Answer 1

1)
given f(x) = 5x^4+x^3+8x-2

By the definition of Big O, f(x) = O(g(x)) if there exists c and n0 such that c*g(x) >= f(n) and n>n0

We can write c*g(x) as 6x^4 which means
=> 6x^4 >= 5x^4+x^3+8x-2

=> Hence c = 6 , Hence f(x) = O(x⁴)

2)
Every time, we take two value and then we check if the value is smaller than its previous element, If Yes, then we swap the element
So it will move the lowest element at the beginning.

The Total time complexity is O(n²)

Thanks, PLEASE COMMENT if there is any concern.