Exercise #6 (No computers needed) Due Friday, 6 Nov, at 11:59pm (3 pts) Complexi
ID: 3760200 • Letter: E
Question
Exercise #6 (No computers needed) Due Friday, 6 Nov, at 11:59pm
(3 pts) Complexity:
1. What is the big – O notation for:
a.) A method that takes exactly 2n2+5n+100 steps
b.) for(i=n;i>0;i=i/2){
//constant time operations ...
}
c.) binary search
d.) for(i=n;i>0;i--){
for(j = m; j > 0; j--) { // m does not vary as n, i.e. it’s independent
//constant time operations
... }
e.) for(i=n;i>0;i--){ for(j = n; j > 0; j--) {
//constant time operations
... }
f.) linearsearch
g.) To find your best friend SoulMatesRUs.com simply tests everyone
against every other Buddy Seeker to find the best matches.
(3 pts) Linked Lists:
Create a doubly linked list. Create an algorithm for each of: a.) Insert at a specified location
b.) Delete a specified node
c.) Delete the last node
(4 pts) Sorting:
You just finished collecting and putting in order the 200 applicants for a new job. The mail intern comes by and drops off 50 more applications that “have to be included”.
Describe an algorithm to sort them first and then how you would put them in the larger stack.
Describe an algorithm to bite the bullet and just put them in one at a time.
Estimate the complexity of each. Is one better? Does it matter for only 250
items?
Explanation / Answer
a) maximum power is n^2, so O(n^2)
b) O(log n) (it's logn wherever divide by 2)
c) O(log n) (everytime search space is getting half)
d) O(nm)
e) O(n^2)
f) O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.