This homework is intended to reinforce
your understanding of Big-O and run-times for algorithms. It is
comprised of various di erent exercises that will ask you to nd the
run-times of loops, explain the run-times of algorithms you have seem
in class, and improve algorithms.
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.
-
Run-time
and Big-O Exercises
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 Algorithm
run-time (Big-O) questions
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 Fibonacci
Sequence
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.
