CSC263 – Week 1, Tutorial 1
Cristyn Howard
Friday, January 12, 2018
Today’s topic: Review of running time, proofs of running time.
• T(n); worst-case running time; the maximum number of steps the algorithm T takes on an input of size n – t(x); the number of steps taken by the algorithm on specific input x
–T(n)=max{t(x) | |x|=n}
• O, Ω, Θ; mathematical concepts that quantify the relations between functions;
– adopted by computer scientists to abstractly compare running time of different algorithms, without
concern for specific implementation details
– O(n2) = {1, 2, n2, 2n2, n2 + 1, …}, (infinite set)
– Ω(n2) = {n2, 2n2, 4n3, …}, (infinite set)
– Θ(n2) = O(n2) ∩ Ω(n2) = {n2, 2n2, …}, (infinite set)
• T(n) ∈ O(g(n)) ⇐⇒ for every input of size n, T takes at most c × g(n) steps, (where c ∈ R)
• T (n) ∈ Ω(g(n)) ⇐⇒ there is some input of size n for which T takes at least c × g(n) steps, (where c ∈ R)
Ex 1:
input: A[1…n] for i = 1 to n:
O(n2) because the max possible iterations of the inner & outer loop result in n2 calls of the fourth line of code, which is in constant time
Ω(n2) because ∀ n,∃ array of 1’s of size n, which will result in runtime of n2
Loop Invariant: at the end of the ith iteration of the while loop, A[last+1 … n] contains the largest elements in A in sorted order
T (n) ∈ O(n2):
• while loop executes at most n times
(each loop reduces ’last’ by 1; when ’last’=1, sorted set true,
for loop not executed, while loop stops) • inner loop executes at most n-1 times
• n(n − 1) ≈ n2
T (n) ∈ Ω(n2):
• consider reverse sorted array of size n
• for 1st iteration of while loop, for loop does n-1 swaps
• for ith iteration of while loop, for loop does n-i swaps
• total swaps reverse sorted array of size n = n n − i = n(n−1) ∈ Θ(n2) i=1 2
• thus for every n, ∃ an input array for which the number of steps is at least ∈ Θ(n2)
Ex 2:
for j = 1 to n:
if A[i] != 1, STOP
Bubblesort(A[1…n]): last = n, sorted = false; while(not sorted):
sorted = true; for j=1 to last-1:
if (A[j] > A[j+1]): swap A[j] & A[j+1]; sorted = false;
last -= 1;
1