CS5800: Algorithms — Iraklis Tsekourakis

Homework 1

Name: Vedansh Kapoor

Instructions:

• Make sure to put your name on the first page. If you are using the LATEX template we provided,
then you can make sure it appears by filling in the yourname command.

• Please review the instructions of the assignment in the pdf description of the assignment.

1
1. (20 points) In the following, use a direct proof (by giving values for c and n0 in the formal
definition of big-O/Ω notation) to prove that:

(a) n2 + 7n + 1 is Ω(n2 )
Solution:

n2 + 7n + 1 is Ω(n2 )
Def: If there is a g(n) such that
0 ≤ f (n) ≥ c · g(n)
for c being any positive real number and n ≥ n0 for n0 being any positive number, then we
say g(n) is asymptotic lower bound of f (n).

g(n) = Ω(f (n)).

Based on the above definition, in order to prove f (n) = n2 + 7n + 1 is Ω(n2 ), we need to prove

f (n) ≥ c · g(n) for n ≥ n0 ,

such that n0 is a positive number and c is a positive real number

Assume c = 0.5
n2 + 7n + 1 ≥ 0.5n2
0.5n2 + 7n + 1 ≥ 0
1 2
n + 7n + 1 ≥ 0 (1)
2
Multiplying (1) by 2,
n2 + 14n + 2 ≥ 0
n2 + 14n + 2 ≥ 0
Roots: √
−b ± b2 − 4ac
n=
2a
p
−14 ± 142 − 4(2)
n=
2·2
√
−14 ± 142 − 8
n=
4
√ √
−14 ± 49 − 2 −7 ± 47
n= =
2 2
n ≈ −3.5 ± (≈ 3.5)
So, one root is n ≈ −7, the other root is n ≈ 0. Since a > 0 for the quadratic equation so after
the root 0 it is increasing.
For n ≥ 1 : f (n) ≥ c · g(n), n ≥ 1
Taking c = 0.5, n0 = 1.
∴ f (n) = Ω(g(n))

2
(b) 3n2 + n − 10 is O(n2 )
Solution:

(b) 3n2 + n − 10 is O(n2 )

Def: If there is a g(n) such that
0 ≤ f (n) ≤ c · g(n)
for c being any positive real number and n ≥ n0 for n0 being any positive number, then we
say f (n) is O(g(n)).
To Prove :
3n2 + n − 10 ≤ c · n2
for c, n0 being any positive constants.
Assume c = 4.
3n2 + n − 10 ≤ 4n2
n2 − n + 10 ≥ 0
Roots: √
−b ± b2 − 4ac
n=
2a
p
2
1 ± (1) − 4(1)(10)
n=
2(1)
Since the discriminant is negative, there are no real roots.
Since there are no roots, the graph is above the x-axis all the time as a > 0.
Hence for any value of n, the curve is never less than 0.
So c = 4, n0 = 1 is valid.

∴ f (n) = O(n2 )

(c) n2 is Ω(n lg n)
Solution:

(c) n2 is Ω(n log n)

f (n) = n2 , g(n) = n log n
Def: If there is a g(n) such that

0 ≤ f (n) ≥ c · g(n), n ≥ n0

for c being any positive real number and n0 being any positive number, we say f (n) is Ω(g(n)).
To Prove :

n2 ≥ c · n log n for n ≥ n0 , c, n0 being positive constants

3
 Assume c = 1.
n2 ≥ n log n
(Assume n is positive) Divide by n
n ≥ log n
n ≥ log n
Since we assume n is positive, n ≥ log n for all n > 0.

∴ f (n) ∈ Ω(g(n))

So c = 1, n0 = 1 is valid.

2. (20 points) Solve the following recurrences using the substitution method. If the given guess is
not correct, you will have to come up with an improved guess that works::

(a) T (n) = T (n−3)+3 lg n. Our guess is T (n) = O(nlgn). Show thatT (n) ≤ cn lg n for some constant
c > 0 (Note that lg n is monotonically increasing for n > 0)
Solution:

Q2: (a)

T (n) = T (n − 3) + 3 log2 n

Guess:
T (n) = O(n log n)
T (n) ≤ c · n log n for c, n0 positive constants.

Using induction: For all k < n, we say

T (k) ≤ c · k log k

For k = n:
T (n) = T (n − 3) + 3 log n
≤ c · (n − 3) log(n − 3) + 3 log n
= (cn − 3c) log(n − 3) + 3 log n
= cn log(n − 3) − 3c log(n − 3) + 3 log n

So,
T (n) ≤ cn log(n − 3) − 3c log(n − 3) + 3 log n
T (n) (1)
cn log(n − 3) − 3c log(n − 3) + 3 log n (2)
cn log(n) − 3c log(n − 3) + 3 log n (3)

4
 Using (1) and (2) and (3), and since log n > log(n − 3) for n > 3,

(1) ≤ (2) ≤ (3) ⇒ (1) ≤ (3)

So,
T (n) ≤ cn log n − 3c log(n − 3) + 3 log n
≤ cn log n − [3c log(n − 3) − 3 log n]

Now to prove above we have to prove,

3c log(n − 3) − 3 log n ≥ 0

3c log(n − 3) ≥ 3 log n
c log(n − 3) ≥ log n
log n
c≥
log(n − 3)

This function’s derivative is negative which means that it is always decreasing and the
function is always positive so for n <= 5, c comes out to be something between 2 and 3 so lets
assume c = 5.
So for c = 5,
3c log(n − 3) − log 3 ≥ 0

Hence,
T (n) ≤ c · n log n

where c = 5 and n0 ≥ 5.

(b) T (n) = 4T (n/3) + n. Our guess is T (n) = O(nlog3 4 ). Show that T (n) ≤ cnlog3 4 for some constant
c>0
Solution:
n
 
T (n) = 4T +n
3
Guess:  
T (n) = O nlog3 4
so,
T (n) ≤ c · nlog3 4

Using Induction,
Assume for all k < n,
T (k) ≤ c · k log3 4

For k = n:  
n
T (n) = 4T 3 +n

5
  log3 4
n
T (n) ≤ 4c 3 +n

4c
T (n) ≤ · nlog3 4 + n
3log3 4

T (n) ≤ c · nlog3 4 + n

T (n) ≤ c · nlog3 4 + n

It is second case where f(n) + g(n) where g(n) > 0 and of the lower order as comp to f(n) then
subtract and prove the same.
New Guess :  
T (n) = O nlog3 4 − d · n
so,
T (n) ≤ c · nlog3 4 − d · n

for some constant d>0, c>0

Using Induction, Assume for all k1 < n,
log3 4
T (k1 ) ≤ c · k1 − d · k1

For k = n:  
n
T (n) = 4T 3 +n

 log3 4
n
T (n) ≤ 4c 3 − 4d · n3 + n

T (n) ≤ c · nlog3 4 − ( 4d
3 − 1)n

So to prove the above as per our guess we need to prove ,

( 4d
3 − 1) = d
4d
3 − d >= 1
4d−3d
3 >= 1
d >= 3

Since d > 0 , hence we proved that

log3 4
T (k1 ) ≤ c · k1 − d · k1 , for d = 3

Therefore ,  
T (n) = O nlog3 4 − d · n, for d = 3

6
3. (20 points) You can also think of insertion sort as a recursive algorithm. In order to sort A[1:n],
recursively sort the subarray A[1:n-1]. Write pseudocode for this recursive version of insertion
sort. Give a recurrence for its worst-case running time.

Solution:
Q3: (i) Pseudocode for recursive function
Recursive Insertion Sort

Input:

A[1..n]: array of n elements (indices start at 1)

i: current index, satisfies 1 ≤ i ≤ n (initially i = {1, 2})

n: number of elements in the array

Output:

Array A sorted in non-decreasing order

Pseudocode:

InsertionSort(A, i, n)
if i ≤ n
Sort(A, i, A[i])
InsertionSort(A, i+1, n)
Sort(A, ind, k)
i = ind − 1
while (i > 0 && A[i] > k)
A[i + 1] = A[i]
i = i −1
A[i + 1] = k

Q3: (ii)

T (n) = T (n − 1) + C
C is the time of everything except te recursive function for that 1 recursive iteration
For best case, the array is already sorted, the so

C = Θ(1)

For worst case, the array is in descending order and each element needs to traverse back to the
start.

7
 First nth iteration,
C = Θ(n)

T (n) = T (n − 1) + Θ(n)

4. (20 points) Let f (n) and g(n) be asymptotically nonnegative functions. Using the basic (formal)
definition of Θ-notation, prove that max f (n), g(n) = Θ(f (n) + g(n))

Solution:
Q4: Asymptotic non-negative meaning
For n ≥ n0 , f (n) ≥ 0

max(f (n), g(n)) = Θ(f (n) + g(n))

To prove Θ, we must prove both O and Ω.
For O:
0 ≤ h(n) ≤ c · j(n), n ≥ n0
where c and n0 are constants.

h(n) = max(f (n), g(n))

j(n) = f (n) + g(n)

h(n) = max(f (n), g(n)), j(n) = f (n) + g(n)

To prove :
h(n) ≥ 0
Since f (n) ≥ 0 for n ≥ n1 , and g(n) ≥ 0 for n ≥ n2 , if nc = max(n1 , n2 ),
then for n ≥ nc ,
f (n) + g(n) ≥ 0 (1)
Hence proved
h(n) ≥ 0
To prove :
h(n) ≤ c · j(n)

max(f (n), g(n)) ≤ c · (f (n) + g(n))

Assume c = 2.
Note: max can have 2 solutions.
When f (n) ≥ g(n),
f (n) ≤ 2(f (n) + g(n))
2(f (n) + g(n)) ≥ f (n)

8
 f (n) + 2g(n) ≥ 0
Since f (n) ≥ 0, g(n) ≥ 0, hence
f (n) + 2g(n) ≥ 0
Similarly, when g(n) > f (n),
2(f (n) + g(n)) ≥ g(n)
Therefore,
max(f (n), g(n)) ≤ 2(f (n) + g(n)), for c = 2, n ≥ nc .
Hence,
max(f (n), g(n)) = O((f (n) + g(n)))
For Ω
To prove:
f (n) + g(n) ≥ 0 for n ≥ nc
(Proved above in eq 1)

0 ≤ h(n) ≥ c · j(n), c, nc are positive constants

h(n) = max(f (n), g(n)), j(n) = f (n) + g(n)

So
h(n) ≥ c · j(n)

max(f (n), g(n)) ≥ c(f (n) + g(n))

Since max has 2 cases, assume c = 21 .
Case 1: f (n) ≥ g(n)
f (n) ≥ 12 (f (n) + g(n))
2f (n) ≥ f (n) + g(n)
f (n) ≥ g(n)
(The above is true as per case 1)
Case 2: g(n) ≥ f (n)

g(n) ≥ 12 (f (n) + g(n))

2g(n) ≥ f (n) + g(n)
g(n) ≥ f (n)
(The above is true as per case 2)
Since
0 ≤ h(n) ≤ c1 · j(n) for c1 = 2, n0 ≥ nc
and
0 ≤ h(n) ≥ c2 · j(n) for c2 = 12 , n0 ≥ nc

9
 Hence we say
h(n) = Θ(j(n))
max(f (n), g(n)) = Θ(f (n) + g(n))

5. (20 points) Is 2n+1 = O(2n )? Is 22n = O(2n )? Use the formal definition of O-notation to answer
these two questions.

Solution:
Q5: (i)

2n+1 = O(2n )
Def:
0 ≤ f (n) ≤ c · g(n)
for c a positive real constant and n ≥ n0 , n0 a positive number. So, f (n) = O(g(n)).
To Prove:
2n+1 ≤ c · 2n
Assume c = 4.

2n+1 ≤ 4 · 2n
4 · 2n − 2n+1 ≥ 0
4 · 2n − 2 · 2n ≥ 0
2 · 2n ≥ 0
For n ≥ 1, 2n ≥ 0.
As 2n ≥ 0 is monotonically increasing for n ≥ 1,

f (n) ≥ 0

Also,
2n+1 ≥ 0 for n ≥ 1
as 2n+1 is monotonically increasing, and at n = 1, 2n+1 = 4 ≥ 0.
Likewise,
2n ≥ 0 for n ≥ 1
Hence proved for c = 4 and n0 = 1,

2n+1 = O(2n )

(ii)
2n = O(2n )
Def:
0 ≤ f (n) ≤ c · g(n)

10
for c being a positive real number and n ≥ n0 , n0 being a positive number. Let

f (n) = 22n , g(n) = 2n

To prove:
22n ≤ c · 2n
Since c is a positive constant and 2 · 2n ≥ 0 for n positive,

22n ≤ c · 2n
Taking square root, √
2n ≤ c · 2 n
√ √
2n ≤ c · 2n
√ √
2n ≤ c
2n ≤ c
But 2n grows faster than any constant c. So after a point,

2n > c no matter how big c is.

Hence,
22n , O(2n )

11