[SOLVED] Homework 6 csci 1112

2.1 Calculate the Big-0 run time of these loops
2.1.1
i=0;
While i < n {
For (j=0;j<n;j++){
Print(this is a loop)
}
i = i*2;
}
2.1.2
Array x = new array[n]
Count = 0;
For (i=0;i<n;i++){
Array[Count] = I;
Count ++
If ( i%3 =0) {
While (Count ! =0) {
Count —
Array[Count] = 0
}
}
}2.2.1
What is the run-time of bubble sort? Explain why in detail.
2
2.2.2
What is the run-time of running binary search on a sorted array? Explain why in detail.
2.2.3
What is the Worst case run-time of Quicksort? Why? What is the average case run-time of Quicksort? Why?2.3.1
Find the Big-O run-time of this program
Public int Fibb ( int x ){
If(x==1) return 1;
If (x==0) return 0;
Return Fibb(x-1)+Fibb(x-2);
}
3
2.3.2
Rewrite this program so that it has a much smaller run-time.
Hint: use an array to store information. O(n) is the optimal solution
2.3.3
Explain the run time of your program.
4