Give an analysis of the running time (Big-Oh notation) for each of the following

Question

Give an analysis of the running time (Big-Oh notation) for each of the following 2 programs. You must provide calculate the computational cost of each line of code that shows how you estimated the code’s running time.

(a) import java.io.*;

public class BubbleSortExample

{ static void bubbleSort(int[] arr)

{ int n = arr.length;

int temp = 0;

for(int i=0; i < n; i++){

for(int j=1; j < (n-i); j++){

if(arr[j-1] > arr[j]){

//swap elements

temp = arr[j-1];

arr[j-1] = arr[j];

arr[j] = temp; } } } }

Explanation / Answer

Solution For Problem :-

Bog-Oh notation for Bellow code :-

public class BubbleSortExample

{ static void bubbleSort(int[] arr)

{ int n = arr.length;

int temp = 0;

for(int i=0; i < n; i++){

for(int j=1; j < (n-i); j++){

if(arr[j-1] > arr[j]){

//swap elements

temp = arr[j-1];

arr[j-1] = arr[j];

arr[j] = temp;

} } } }

Here two for loops are running that means n*n but according to the code the loops are running like this.

when i=0 inner loop repeats n times when i=1 then n-1 when i=2 then n-2 .

.`. n+(n-1)+(n-2)+(n-3).............+1

= (n*(n + 1))/2

=O(n^2)

The Big-Oh notation for above code is = O(n^2)   This is worst case analysis.

Thank you!

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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