In the tapestry of algorithms, two names resound, Benji Tusk and Eyal Schachter, profound, Their minds, a symphony of intellect’s grace, Embark on a journey, a recursive embrace.
With pens poised and hearts alight,
They venture into complexity’s sight,
In the realm where algorithms dance and weave,
They seek the rhythm their minds perceive.
Recursive melodies, they aim to divine,
In the labyrinth of time, where patterns entwine,
Benji’s insight, a beacon so bright,
Eyal’s logic, a guiding light.
Together they traverse the recursive maze,
In pursuit of truths, in myriad ways,
Analyzing runtimes, each algorithm’s flight,
In the waltz of complexities, they find delight.
From towering structures to intricacies small,
They unravel the mysteries, they heed the call,
In the tapestry of data, where brilliance gleams,
Benji Tusk and Eyal Schachter, dreamers of dreams.
Eyal Schachter (209792266) and Benji Tusk (650282680)
Question One
Part A
T(n)a=2b=2f(n)=n3nlogbaf(n)for any 0<a⋅f(bn)We can can take any ∴T(n)=2T(2n)+n3=nlog22=n1=n=Ω(n1+ϵ)(Case III)ϵ<2=2(2n)3=223n3=22n3=4n3c between 41 and 1=Θ(n3)
Part B
T(n)=T(3n)+2logn
We cannot use the Master Method, so we use iteration:
T(n)…T(n)∴T(n)=T(3n)+2logn=T(32n)+2log3n+2logn=T(3in)+j=0∑i−12log3jn=T(3in)+2[j=0∑i−1(logn−log3j)]=T(3in)+2[j=0∑i−1logn−j=0∑i−1log3j]=T(3in)+2[ilogn−j=0∑i−1log3j]=T(3in)+2ilogn−2j=0∑i−1log3j=T(3in)+2ilogn−2j=0∑i−1jlog(3)=T(3in)+2ilogn−2log(3)j=0∑i−1j=T(3in)+2ilogn−2log(3)2i2−i=T(3in)+2ilogn−log(3)⋅(i2−i)Bottom Row is where i=log3(n)=T(1)+2⋅log3n⋅log2n−log23(log32n−log3n)≤2⋅log3n⋅log2n−log23⋅log32n+log23⋅log3n=2⋅log3n⋅log32log3n−log321⋅log32n+log321⋅log3n=log322⋅log32n−log321⋅log32n+log321⋅log3n=log321⋅log32n+log321⋅log3n≤log321⋅log32n=log3⋅(log3logn)2=log31⋅log2n≤clog2nfor c≥log3−13=O(log2(n))
Since I cannot be bothered to transcribe the math, you’re just gonna have to deal with the pictures. Hope the poem at the top makes up for this 🙃
The general form of the recurrence is T(n)=T(n−k)+sort(k)+n where k is the number of elements to the left of the partition, and sort(k) the time taken by the sorting algorithm.
We will calculate worst-case scenario, where there is no early exit (eg i=n).
We will examine a few cases:
Case 1
k=1,sort(k)=k2 (bubble sort)
The recurrence is T(n)=T(n−1)+12+n=T(n−1)+θ(n)
Using iteration, the general form is T(n)=T(n−i)+∑j=0i−1θ(n−j)
We can continue until i=n−1 (note i here has no relation to i from the question). T(n)=T(1)+∑j=0n−2θ(n−j)=d1+∑j=0n−2d2(n−j)=d1+d2∑j=2n(j)≤d2n2
So T(n)=O(n2)
Case 2
k=2n, sort(k)=klogk=2nlog(2n) (merge sort)
The recurrence is T(n)=T(2n)+2nlog(2n)+n
Which simplifies to T(2n)+2n(logn+1).
We use the master method, where a=1,b=2,f(n)=2n(logn+1). nlogba=n0=1 f(n)=Ω(nϵ)∣0<ϵ≤1 (Case III of Master Method)
We now check for regularity: 1⋅f(2n)≤c⋅f(n) 4n(log(2n)+1)=4n(logn−1+1)≤c2n(logn+1)
For 21≤c<1.
So, T(n)=O(2n(logn+1))=O(nlogn)
Case 3
k=2n, sort(k)=k2=(2n)2 (bubble sort)
The recurrence is T(n)=T(2n)+(2n)2+n
Which simplifies to T(2n)+4n2+4n.
We use the master method, where a=1,b=2,f(n)=4n2+4n. nlogba=n0=1 f(n)=Ω(nϵ)∣0<ϵ≤2 (Case III of Master Method)
We now check for regularity: 1⋅f(2n)≤c⋅f(n) 16n2+8n≤c4n2+4n
For 21≤c<1.
So, T(n)=O(4n2+4n)=O(n2)
Case 4
k=n−1, sort(k)=klogk
Since this is pretty much our ‘early exit’ case, the computation is immediate: T(n)=T(n−k)+sort(k)+n=T(1)+(n−1)log(n−1)+n=O(nlogn)