Due: January 16, 23:59 Atlantic time, in Crowdmark.

This assignment is to remind you of the background material you from the prerequisite courses. We will not need all of this right away, but if you find one of these questions particularly difficult, that’s a hint to do some background reading.

Use the fact that for \(n \geq 4\), \(n^2 \leq 2^n\) to prove formally that \(n \lg(n) \in O(n^2)\), i.e. give constants \(c\) and \(n_0\) and show that for all integers \(n≥n_0\), \(n \lg(n) \leq cn^2\).

Prove formally that \(n \sqrt{n} \in O(n^2)\), i.e. give constants \(c\) and \(n₀\) and show that for all integers \(n \geq n₀\), \(n \sqrt{n} \leq n^2\).

Analyse the worst case time complexity of the following version of bubblesort. Give an upper (i.e. O) bound. Here is a Python implementation of bubblesort (see the text for a pseudocode version).

def bubble(A):
    n=len(A)
    for i in range(0,n-1):
        for j in range(n-1,i,-1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]

if __name__=="__main__":
    from random import randrange
    A = [ randrange(10,100) for i in range(12) ]
    bubble(A)
    print(A)

Suppose Professor Grumpy wants to shuffle the seating of \(n\) students in their Algorithms class (who can understand why Prof G does what they do). They have a “uniform” shuffling algorithm which assigns each student to a given seat with probability \(1/n\). Use linearity of expectation (C.24 in Cormen) to calculate the expected number of students who get to stay in their current seat.