Problem 6

Write down the running time equation, T(n), of the program do_something below. Note that list's pop takes constant ( (1) ) time.

def do_something(L): if len(L) < 2: return 1 total = 0 for x in L: total += x first = L.pop(0) last = L.pop(-1) if first==last: return total + do_something(L) else: return 2*total + do_something(L)

Problem 7

Write a Python function to sort numbers in decreasing order, based on the following recursive strategy:

Note: this strategy returns a list, which is in decreasing order.

Check the smallest case(s), and return the proper sorted output. The smallest cases is when you cannot reduce the input list in your recursive strategy.

Recursive strategy when the input L is still reducible in size:

Find the largest number in the input list, L. Use Python's built-in max function to do this.

Remove the largest number. Use Python's remove method of lists to do this.

After you remove the largest, L has one item fewer, i.e. you've "reduced" the input size of L.

Use "the same recursive strategy" to get a sorted list of the remaining numbers in L.

Assemble the largest number and the sorted list of the remaining numbers to construct a sorted list of L.

Examples:

sort_max([10, 5, 7, 12]) returns [12, 10, 7, 5]

sort_max([5]) returns [5]

sort_max([]) returns []

Examples of Python's functions:

L = [1,4,10,3]

max(L) returns 10

L.remove(10) removes 10 from L. This method returns None.

List concatenation: [1] + [2, 3] --> [1, 2, 3]

Note: this problem is not meant to produce the best way to sort a list. It's meant to orient you toward a recursive mindset, which is helpful for more complex problems.

[12]:

#

# Input: a list of numbers

# Output: the same list of numbers, but in decreasing order

#

def sort_max(L):

 pass