Description

Introduction
This homework is intended to reinforce your understanding of BigO and runtimes for algorithms. It is comprised of various di erent exercises that will ask you to nd the runtimes of loops, explain the runtimes of algorithms you have seem in class, and improve algorithms.
1.1 Deadline
November 15, 2019 at 11:59pm
1.2 Submission
You must turn in a pdf le with your answers on it.
1.3 Grading Rubric
Grading will be based o of both correct answers as well as answer completion. Be sure to show all over your work and explain things thoroughly. Incomplete answers will not receive full credit.
1.4 Plagarism
We will use a set of automated tools speci cally designed to analyze solutions for plagarism. If you copy code from another source, classmate or website, there is a very high probability that these tools will ag your work as plagarized. You are permitted to discuss the problems at a high level; however, you must write your own solution. If you do not share answers or outright borrow answers from a website, you will have no problem with the plagarism lter.
1
2.1 Calculate the Big0 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 Algorithm runtime (BigO) questions
2.2.1
What is the runtime of bubble sort? Explain why in detail.
2
2.2.2
What is the runtime of running binary search on a sorted array? Explain why in detail.
2.2.3
What is the Worst case runtime of Quicksort? Why? What is the average case runtime of Quicksort? Why?
2.3 Fibonacci Sequence
2.3.1
Find the BigO runtime of this program
Public int Fibb ( int x ){
If(x==1) return 1;
If (x==0) return 0;
Return Fibb(x1)+Fibb(x2);
}
3
2.3.2
Rewrite this program so that it has a much smaller runtime.
Hint: use an array to store information. O(n) is the optimal solution
2.3.3
Explain the run time of your program.
4