For each of the following algorithms write its running time as a mathematical fu

Question

For each of the following algorithms write its running time as a mathematical function of the input size (n), considering worst case scenario. 1) Sorted array: Linear search. 2) Assume myA is an integer array that has been created earlier and myR is a random generator object also has been created earlier. for(int I = myA.length: I > = 0: i/= 2) binarySearch(myA, myR.nextInt (1000)): } 3) Use the same array as in part 2 above. for (int i = 0: I has been created earlier and put to full state before the following code: while(!myQ.isEmpty){ myQ.dequeue(): myQ.dequeue(): myQ.dequeue(myR.nextInt(1000)): }

Explanation / Answer

1.
Sorted array: Linear Search in worst case have running in order of O(n)

2.
for(int i=myA.length; i>=0; i /= 2){ // runs log(n) times
   binarySearch(myA, myR.nextInt(1000)); //consumes log(n) amount of time
}

//so total time = (log n)2

3.
for(int i=0; i<8; ++i){ //loops 8 number of times
   selectionSort(myA, myA.length); //consumes n2 amount of time
   insertionSort(myA, 0, myA.length-1); //since the array is already sorted by selectionsort, insertion sort consumes only O(n) time
}
/*
So total amount of time = 8 * (n2 + n) = 8n2 + n = O(n2)
*/

4.
In a well programmed Circular Queue,
enqueue takes O(1) amount of time,
dequeue takes O(1) amount of time,
isEmpty takes O(1) amount of time,

so
while( !myQ. isEmpty ){ //O(1) for function call and loops n mumber of times since every time in the loop the effective pop is 1 item (2 poped and 1 pushed), So only after looping n number of times, the queue would be empty.
   myQ.dequeue(); //O(1) for function call
   myQ.dequeue();//O(1) for function call
   myQ.enqueue(myR.nextInt(1000));//O(1) for function call
}

/*
Complexity is n * (1 + 1 + 1) = 3n = O(n)
*/

I hope this helps you. In case of any triuble, let me know

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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