Question

okay, this should be pretty quick, what did ya'll get for the first few questions on the problem set 7 review?

Answer 1

I got the first two as being linear O(i), number 3 was quadratic: O(s^2), and 4 was also quadratic O(s1^3 * s2^3) or if s1=s2, O(s^6)

Answer 2

1.) Linear or O(n) because the recursion counts down 1 at a time
2.) Linear or O(n) because the while loop decrements by 1 each time.
3.) Linear because the for statement goes through exhaustive enumeration once.
4.) same as 4. O(n)

Answer 3

edit:
4.) same as 3 (my bad)

Answer 4

Wait really? 3 and 4 are linear? I thought that since (3) had nested functions (searching through the entire list 'res' for each element of the list 's'), that it would be quadratic. And since the complexity of (3) had to be taken into account when finding the complexity for (4), I thought that (4) definitely had to be quadratic.

Answer 5

yes because problem 3 and 4 rely on the amount of n times and that is the maximum times we have to search for the solution. I could be wrong but i dont think so considering 7 out of the 8 people at http://curiousreef.com/class/mit-opencourseware-600-introduction/ have the same answer as me... The other person put linear, linear, linear, and exponential for #4