CSC263 Tutorial 1
Big-O, Ω, Θ
Trevor Brown (tabrown@cs.utoronto.ca)
The algorithm takes at most c*x steps to run on the worst possible input.
The algorithm takes at least c*x steps to run on the worst possible input.
Big-O and Big-Ω
• ManystudentsthinkBig-Ois“worstcase”andBig-Ω is “best case.” They are WRONG! Both O(x) and Ω(x) describe running time for the worst possible input!
• What do O(x) and Ω(x) mean?
Algorithm is O(x)
Algorithm is Ω(x)
• How do we show an algorithm is O(x) or Ω(x)?
Algorithm is O(x)
Algorithm is Ω(x)
Show: for every input, the algorithm takes at most c*x steps.
Show: there is an input that makes the algorithm take at least c*x steps.
Analyzing algorithms using O, Ω, Θ • First,weanalyzesomeeasyalgorithms.
• Wecaneasilyfindupperandlowerbounds on the running times of these algorithms by using basic arithmetic.
Example 1 print *
for i = 1..100
• Running time: 100*c, which is Θ(1) (why?) • O(1), Ω(1) => Θ(1)
for i = 1..x print *
• Running time: x*c
• O(x), Ω(x) => Θ(x)
Example 2
• In fact, this is also Ω(1) and O(n^2), but these are very weak statements.
x
for i = 1..x
for j = 1..x
print *
• O(x^2), Ω(x^2) => Θ(x^2) x
Example 3
x
for i = 1..x
for j = 1..i
print *
Example 4a
• Big-O: i is always ≤ x, so j always iterates up to at most x, so this at most x*x steps, which is O(x^2).
• Big-Ω:
• When i=1, the loop over j performs “print *” once.
• When i=2, the loop over j performs “print *” twice. […] • So, “print *” is performed 1+2+3+…+x times.
• Easy summation formula: 1+2+3+…+x = x(x+1)/2
• x(x+1)/2 = x^2/2+x/2 ≥ (1/2) x^2, which is Ω(x^2)
for i = 1..x
for j = 1..i
>= for i = x/2..x
for j = 1..x/2
print *
print * j ≤ x/2
• Big-Ω:
– Useful trick: consider the iterations of the
first loop for which i >= x/2.
– In these iterations, the second loop iterates from j=1 to at least j=x/2.
– Therefore, the number of steps performed in these iterations is at least x/2*x/2 = (1/4)
i ≥ x/2
x^2, which is Ω(x^2).
Example 4b
x/2 – The time to perform ALL iterations is even
more than this so, of course, the whole algorithm must take Ω(x^2) time.
– Therefore, this function is Θ(x^2).
x/2
for i = 1..x
for j = 1..i
for i = x/2..x
for j = x1/..4ix./.x2/2
for k = 1..j print *
for k = 1..jx/4 print *
Example 5
• Big-O: i, j, k ≤ x, so we know total number of steps is ≤ x*x*x = O(x^3). • Big-Ω:
– Consider only the iterations of the first loop from x/2 up to x.
– For these values of i, the second loop always iterates up to at least x/2.
– Consider only the iterations of the second loop from x/4 up to x/2.
– For these values of j, the third loop always iterates up to at least x/4.
– For these values of i, j and k, the function performs “print *” at least: x/2 * x/4 * x/4 = x^3/32 times, which is Ω(x^3).
– Therefore, this function is Θ(x^3).
Analyzing algorithms using O, Ω, Θ
• Now,wearegoingtoanalyzealgorithms whose running times depend on their inputs.
• Forsomeinputs,theyterminateveryquickly. • Forotherinputs,theycanbeslow.
LinearSearch(A[1..n], key) for i = 1..n
Example 1
if A[i] = key then return true return false
• Mighttake1iteration…mighttakemany…
• Big-O:atmostniterations,constantworkper
iteration, so O(n)
• Big-Ω:canyoufindabadinputthatmakesthe algorithm take Ω(n) time?
Example 2 binarySearch(A, i)
int A[n] for i = 1..n
• Remember: binarySearch is O(lg n).
• O(n lg n)
• How about Ω?
• Maybeit’sΩ(nlgn),butit’shardtotell.
• Not enough to know binary search is Ω(lg n), because the worst-case input might make only one invocation of binary search take c*lg n steps (and the rest might finish in 1 step).
• Wouldneedtofindaparticularinputthatcausesthe algorithm to take a total of c(n lg n) steps.
• Infact,binarySearch(A,i)takesc*lgnstepswheniisnotinA, so this function takes c(n lg n) steps if A[1..n] doesn’t contain any number in {1,2,…,n}.
Example 3
• Your boss tells you that your group needs to develop a sorting algorithm for the company’s web server that runs in O(n lg n) time.
• Ifyoucan’tprovethatitcansortanyinputof length n in O(n lg n) time, it’s no good to him. He doesn’t want to lose orders because of a slow server.
• Your colleague tells you that he’s been working on this piece of code, which he believes should fit the bill. He says he thinks it can sort any input of length n in O(n lg n) time, but he doesn’t know how to prove this.
WeirdSort(A[1..n]) last := n
sorted := false while not sorted do
Example 3 continued
sorted := true
for j := 1 to last-1 do
if A[j] > A[j+1] then swap A[j] and A[j+1] sorted := false
last := last-1