COURSE CODE: CSC 803

COURSE TITLE:
ANALYSIS OF ALGORITHMS
COURSE INSTRUCTOR:
DR. MUHAMMAD ALIYU SULEIMAN

DEPARTMENT OF COMPUTER SCIENCE

NILE UNIVERSITY OF NIGERIA
COMPUTATIONAL COMPLEXITY II

WEEK THREE

2
SURVEY OF COMMON RUNNING TIMES

3
Constant time CONSTANT TIME

Constant time. Running time is O(1).

bounded by a constant,
Examples. which does not depend on input size n

・Conditional branch.
・Arithmetic/logic operation.
・Declare/initialize a variable.
・Follow a link in a linked list.
・Access element i in an array.
・Compare/exchange two elements in an array.
・…
Linear time
LINEAR TIME
Linear time. Running time is O(n).

Merge two sorted lists. Combine two sorted linked lists A = a1, a2, …, an and
B = b1, b2, …, bn into a sorted whole.

O(n) algorithm. Merge in mergesort.

i ← 1; j ← 1.
WHILE (both lists are nonempty)
IF (ai ≤ bj) append ai to output list and increment i.
ELSE append bj to output list and increment j.
Append remaining elements from nonempty list to output list.
32
TARGET SUM TARGET SUM
TARGET-SUM. Given a sorted array of n distinct integers and an integer T,
find two that sum to exactly T ?

input
20 10 20 30 35 40 60 70 T = 60
(sorted)

i j
TARGET SUM
TARGET SUM…
TARGET-SUM. Given a sorted array of n distinct integers and an integer T,
find two that sum to exactly T ?

O(n2) algorithm. Try all pairs.

O(n) algorithm. Exploit sorted order.

input
20 10 20 30 35 40 60 70 T = 60
(sorted)

i j

Invariant. No element to the left of i or right of j in pair that sums to T.

Logarithmic time
LOGARITHMIC TIME
Logarithmic time. Running time is O(log n).

Search in a sorted array. Given a sorted array A of n distinct integers and an

integer x, find index of x in array.

remaining elements
O(log n) algorithm. Binary search.
・Invariant: If x is in the array, then x is in A[lo .. hi].
・After k iterations of WHILE loop, (hi − lo + 1) ≤ n / 2k k ≤ 1 + log2 n.

lo ← 1; hi ← n.
WHILE (lo ≤ hi)
mid ← ⎣(lo + hi) / 2⎦.
IF (x < A[mid]) hi ← mid − 1.
ELSE IF (x > A[mid]) lo ← mid + 1.
ELSE RETURN mid.
RETURN −1.
35
SEARCH IN A SORTED ROTATED ARRAY
SEARCH IN A SORTED ROTATED ARRAY
SEARCH-IN-SORTED-ROTATED-ARRAY. Given a rotated sorted array of n distinct
integers and an element x, determine if x is in the array.

sorted circular array

20 30
95

90

35
50
85
80

60
65
75 67

sorted rotated array

80 85 90 95 20 30 35 50 60 65 67 75

1 2 3 4 5 6 7 8 9 10 11 12
SEARCH IN A SORTED ROTATED ARRAY
SEARCH IN A SORTED ROTATED ARRAY…
SEARCH-IN-SORTED-ROTATED-ARRAY. Given a rotated sorted array of n distinct
integers and an element x, determine if x is in the array.

O(log n) algorithm.
・Find index k of smallest element.
・Binary search for x in either A[1 .. k−1] or A[k .. n].
find index of smallest element

lo ← 1; hi ← n.
IF (A[lo] ≤ A[hi]) RETURN 0 sorted

WHILE (lo + 2 ≤ hi) at least 3 elements

mid ← ⎣(lo + hi) / 2⎦.

loop invariant
IF (A[mid] < A[hi]) hi ← mid. A[lo] > A[hi]

ELSE IF (A[mid] > A[hi]) lo ← mid.

RETURN hi
 Linearithmic time
LINEARITHMIC TIME
Linearithmic time. Running time is O(n log n).

Sorting. Given an array of n elements, rearrange them in ascending order.

O(n log n) algorithm. Mergesort.

a[]
lo hi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
M E R G E S O R T E X A M P L E
ge(a, aux, 0, 0, 1) E M R G E S O R T E X A M P L E
ge(a, aux, 2, 2, 3) E M G R E S O R T E X A M P L E
(a, aux, 0, 1, 3) E G M R E S O R T E X A M P L E
ge(a, aux, 4, 4, 5) E G M R E S O R T E X A M P L E
ge(a, aux, 6, 6, 7) E G M R E S O R T E X A M P L E
(a, aux, 4, 5, 7) E G M R E O R S T E X A M P L E
, aux, 0, 3, 7) E E G M O R R S T E X A M P L E
ge(a, aux, 8, 8, 9) E E G M O R R S E T X A M P L E
ge(a, aux, 10, 10, 11) E E G M O R R S E T A X M P L E
(a, aux, 8, 9, 11) E E G M O R R S A E T X M P L E
ge(a, aux, 12, 12, 13) E E G M O R R S A E T X M P L E
ge(a, aux, 14, 14, 15) E E G M O R R S A E T X M P E L
(a, aux, 12, 13, 15) E E G M O R R S A E T X E L M P
, aux, 8, 11, 15) E E G M O R R S A E E L M P T X
aux, 0, 7, 15) A E E E E G L M M O P R R S T X
Trace of merge results for top-down mergesort 3
LARGEST EMPTY INTERVAL
LARGEST EMPTY ARGEST L E
INTERVAL MPTY INTERVAL

LARGEST-EMPTY-INTERVAL. Given n timestamps x1, …, xn on which copies of a

LARGEST
file -EMPTY
arrive at a -I
server, . Given
what
NTERVAL n timestamps
is largest interval when xn on
x1, …, no which
copies of copies of a
file arrive?
file arrive at a server, what is largest interval when no copies of file arrive?

O(n log n) algorithm.

・Sort the array a.
・Scan the sorted list in order, identifying the maximum gap between
successive timestamps.
Quadratic time
QUADRATIC TIME
Quadratic time. Running time is O(n2).

Closest pair of points. Given a list of n points in the plane (x1, y1), …, (xn, yn),
find the pair that is closest to each other.

O(n2) algorithm. Enumerate all pairs of points (with i < j).

min ← ∞.
FOR i = 1 TO n
FOR j = i + 1 TO n
d ← (xi − xj)2 + (yi − yj)2.
IF (d < min)
min ← d.

Remark. Ω(n2) seems inevitable, but this is just an illusion. [see §5.4]
4
Cubic time
CUBIC TIME
Cubic time. Running time is O(n3).

3-SUM. Given an array of n distinct integers, find three that sum to 0.

O(n3) algorithm. Enumerate all triples (with i < j < k).

FOR i = 1 TO n
FOR j = i + 1 TO n
FOR k = j + 1 TO n
IF (ai + aj + ak = 0)
RETURN (ai, aj, ak).

Remark. Ω(n3) seems inevitable, but O(n2) is not hard. [see next slide]
3-SUM
3-SUM
3-SUM. Given an array of n distinct integers, find three that sum to 0.

O(n3) algorithm. Try all triples.

O(n2) algorithm.
・Sort the array a.
・For each integer ai : solve TARGET-SUM on the array containing all
elements except ai with the target sum T = −ai.

Best-known algorithm. O(n2 / (log n / log log n)).

Conjecture. No O(n2−ε) algorithm for any ε > 0.
Polynomial time
POLYNOMIAL TIME
Polynomial time. Running time is O(nk) for some constant k > 0.

Independent set of size k. Given a graph, find k nodes such that no two
are joined by an edge.
k is a constant

O(nk) algorithm. Enumerate all subsets of k nodes.

FOREACH subset S of k nodes:

Check whether S is an independent set.
IF (S is an independent set)
RETURN S.
independent set of size 3

・Check whether S is an independent set of size k takes O(k2) time.

・Number of k-element subsets = n = n(n 1)(n 2) · · · (n k + 1) nk

・O(k2 nk / k!) = O(nk). k k(k 1)(k 2) · · · 1 k!

poly-time for k = 17, but not practical 46

Exponential time EXPONENTIAL TIME
k
Exponential time. Running time is O(2n ) for some constant k > 0.

Independent set. Given a graph, find independent set of max size.

O(n2 2n) algorithm. Enumerate all subsets of n elements.

S* ← ∅.
FOREACH subset S of n nodes:
Check whether S is an independent set.
IF (S is an independent set and ⎢S⎟ > ⎢S*⎟)
S* ← S. independent set of max size
RETURN S*.
Exponential time EXPONENTIAL TIME…
k
Exponential time. Running time is O(2n ) for some constant k > 0.

Euclidean TSP. Given n points in the plane, find a tour of minimum length.

O(n ! n!) algorithm. Enumerate all permutations of length n.

π* ← ∅.
FOREACH permutation π of n points:
Compute length of tour corresponding to π.
IF (length(π) < length(π*))
π* ← π.
for simplicity, we’ll assume Euclidean
RETURN π*. distances are rounded to nearest integer
(to avoid issues with infinite precision)

48
AnalysisANALYSIS
of algorithms: quiz 4
OF ALGORITHMS: QUIZ 4
Which is an equivalent definition of exponential time?

A. O( 2n) doesn’t include 3n

B. O(2cn ) for some constant c > 0. includes 3n but doesn’t

C. Both A and B.

D. Neither A nor B.
INSERTSORT

20
 INSERTION SORT
• As stated in Observation 1.3 above, the number of
comparisons performed by Algorithm selectionsort is
exactly n(n − 1)/2 regardless of how the elements of the
input array are ordered.

• Another sorting method in which the number of

comparisons depends on the order of the input elements
is the so-called INSERTIONSORT.

• This algorithm, which is shown below, works as follows.

• We begin with the subarray of size 1, A[1], which is
already sorted.
 INSERTION SORT…
• Next, A[2] is inserted before or after A[1] depending on
whether it is smaller than A[1] or not.

• Continuing this way, in the ith iteration, A[i] is inserted

in its proper position in the sorted subarray A[1..i − 1].

• This is done by scanning the elements from index i − 1

down to 1, each time comparing A[i] with the element
at the current position.

• In each iteration of the scan, an element is shifted one

position up to a higher index.
 INSERTION SORT…
• This process of scanning, performing the comparison
and shifting continues until an element less than or
equal to A[i] is found or when all the sorted sequence
so far is exhausted.

• At this point, A[i] is inserted in its proper position, and

the process of inserting element A[i] in its proper place
is complete.
 14 INSERTION SORT…
Algorithms: Design Techniques and Analysis

Algorithm 1.5 insertionsort

Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
1. for i ← 2 to n
2. x ← A[i]
3. j← i − 1
4. while (j > 0) and (A[j] > x)
5. A[j + 1] ← A[j]
6. j←j − 1
7. end while
8. A[j + 1] ← x
9. end for

• Unlike Algorithm selectionsort, the number of element

Unlike Algorithm selectionsort, the number of element comparisons
comparisons
done by Algorithmdone by Algorithm
insertionsort dependsINSERTIONSORT
on the order of the input ele-
ments. It is easy to see that the number of element comparisons is mini-
depends
mum whenon the the
array order ofsorted
is already the ininput elements.
nondecreasing order. In this case,
the number of element comparisons is exactly n − 1, as each element A[i],
2 ≤ i ≤ n, is compared with A[i − 1] only. On the other hand, the maxi-
mum number of element comparisons occurs if the array is already sorted
 INSERTION SORT…
• It is easy to see that the number of element
comparisons is minimum when the array is already
sorted in nondecreasing order.

• In this case, the number of element comparisons is

exactly n − 1, as each element A[i], 2 ≤ i ≤ n, is
compared with A[i − 1] only.

• On the other hand, the maximum number of element

comparisons occurs if the array is already sorted in
decreasing order and all elements are distinct.
 INSERTION SORT…
• In this case, the number of element comparisons is
n n−1
n(n − 1)
∑ ∑
i−1= i=
i=2 i=1
2

• On as each element A[i], 2 ≤ i ≤ n, is compared with

each entry in the subarray A[1..i − 1].

• This number coincides with that of Algorithm

selectionsort.
 INSERTION SORT…
• As to the number of element assignments, notice that
there is an element assignment after each element
comparison in the while loop.

• Moreover, there are n − 1 element assignments of A[i]

to x in Step 2 of the algorithm.

• It follows that the number of element assignments is

equal to the number of element comparisons plus
n − 1.
 INSERTION SORT…
Observation 1.4:

The number of element comparisons performed by

Algorithm INSERTIONSORT is between n − 1 and
n(n − 1)/2.

• The number of element assignments is equal to the

number of element comparisons plus n − 1 .
THE O − Notation

29
 THE O − Notation
• We have seen in the previous slide (Observation 1.4)
that the number of elementary operations performed

by Algorithm INSERTIONSORT is at most cn 2, where c is

some appropriately chosen positive constant.

• In this case, we say that the running time of Algorithm

INSERTIONSORT is O(n 2) (read “Oh of n 2” or “big-Oh of

n 2 ”).
• This can be interpreted as follows:
 THE O − Notation…
‣ Whenever the number of elements to be sorted is
equal to or exceeds some threshold n0, the running

time is at most cn 2 for some constant c > 0.

• It should be emphasized, however, that this does not

mean that the running time is always as large as cn 2,
even for large input sizes.

• Thus, the O − notation provides an upper bound on

the running time; it may not be indicative of the actual
running time of an algorithm.
 THE O − Notation…
‣ For example, for any value of n, the running time of
Algorithm INSERTIONSORT is O(n) if the input is
already sorted in nondecreasing order.

• In general, we say that the running time of an algorithm

is O(g(n)), if whenever the input size is equal to or
exceeds some threshold n0, its running time can be

bounded above by some positive constant c times g(n).

The formal definition of this notation is as follows.
 THE O − Notation…
Definition 1.2

• Let f(n) and g(n) be two functions from the set of natural
numbers to the set of nonnegative real numbers.

• f(n) is said to be O(g(n)) if there exists a natural number n0 and

a constant c > 0 such that.

∀n ≥ n0, f(n) ≤ cg(n)

Consequently, if lim f(n)/g(n) exists, then

n→∞

f(n)
lim ≠ ∞ implies f(n) = O(g(n)).
n→∞ g(n)
 THE O − Notation…
• Informally, this definition says that f grows no faster than
some constant times g.

• The O − notation can also be used in equations as a

simplification tool.

• For instance, instead of writing

f(n) = 5n 3 + 7n 2 − 2n + 13,

• we may write f(n) = 5n 3 + O(n 2).

• This is helpful if we are not interested in the details of the

lower-order terms.
THE Ω − Notation

35
 THE Ω-NOTATION
• While the O − notation gives an upper bound, the
Ω − notation, on the other hand, provides a lower
bound within a constant factor of the running time.

• We have seen Observation 1.4 that the number of

elementary operations performed by Algorithm
INSERTIONSORT is at least cn, where c is some
appropriately chosen positive constant.

• In this case, we say that the running time of Algorithm

INSERTIONSORT is Ω(n) …
 THE Ω-NOTATION…
• …(read “omega of n”, or “big-omega of n”).

• This can be interpreted as follows:

‣ Whenever the number of elements to be sorted is

equal to or exceeds some threshold n0, the running

time is at least cn for some constant c > 0.

• As in the O − notation, this does not mean that the

running time is always as small as cn.

• Thus, the Ω − notation provides a lower bound on the

running time;
 THE Ω-NOTATION…
‣ it may not be indicative of the actual running time of
an algorithm.

• For example, for any value of n, the running time of

Algorithm INSERTIONSORT is Ω(n 2) if the input consists
of distinct elements that are sorted in decreasing order.

• In general, we say that an algorithm is Ω(g(n)), if

whenever the input size is equal to or exceeds some
threshold n0, its running time can be bounded below by

some positive constant c times g(n).

 THE Ω-NOTATION…
• This notation is widely used to express lower bounds on
problems as well.

• In other words, it is commonly used to state a lower

bound for any algorithm that solves a specific problem.

• For example, we say that the problem of matrix

multiplication is Ω(n 2).

‣ This is a shorthand for saying “any algorithm for

multiplying two n × n matrices is Ω(n 2)”.
 THE Ω-NOTATION…
• Likewise, we say that the problem of sorting by
comparisons is Ω(nlogn), to mean that no comparison-
based sorting algorithm with time complexity that is
asymptotically less than nlogn can ever be devised.

• The formal definition of this notation is symmetrical to

that of the O-notation.
 THE Ω-NOTATION…
Definition 1.3

• Let f(n) and g(n) be two functions from the set of

natural numbers to the set of nonnegative real
numbers.

• f(n) is said to be Ω(g(n)) if there exists a natural

number n0 and a constant c > 0 such that:

∀n ≥ n0 , f(n) ≥ cg(n).

Consequently, if lim f(n)/g(n) exists, then

n→∞
 THE Ω-NOTATION…
f(n)
lim ≠ 0 implies f(n) = Ω(g(n)).
n→∞ g(n)

• Informally, this definition says that f grows at least as

fast as some constant times g. It is clear from the
definition that f(n) is Ω(g(n)) iff g(n) is O( f(n)) .
THE Θ − Notation

43
 THE Θ − Notation
• We have seen before that the number of element
comparisons performed by Algorithm selectionsort is
always proportional to n2 (Observation 1.3).

• Since each element comparison takes a constant

amount of time, we say that the running time of

Algorithm SELECTIONSORT is Θ(n 2) (read “theta of n 2”).

• This can be interpreted as follows.

‣ There exist two constants c1 and c2 associated with

the algorithm…
 THE Θ − Notation…
• …with the property that on any input of size n ≥ n0, the

running time is between c1n 2 and c2n 2.

• These two constants encapsulate many factors

pertaining to the details of the implementation of the
algorithm and the machine and technology used.

• By Observation 1.3, the number of element

comparisons performed by Algorithm BOTTOMUPSORT
is proportional to nlogn.
 THE Θ − Notation…
• In this case, we say that the running time of Algorithm
BOTTOMUPSORT is Θ(nlogn).

• In general, we say that the running time of an algorithm

is of order Θ(g(n)) if whenever the input size is equal
to or exceeds some threshold n0, its running time can

be bounded below by c1g(n) and above by c2g(n),

where 0 < c1 ≤ c2.

 THE Θ − Notation…
• Thus, this notation is used to express the exact order
of an algorithm, which implies an exact bound on its
running time.

• The formal definition of this notation is as follows.

Definition 1.4

• Let f(n) and g(n) be two functions from the set of

natural numbers to the set of nonnegative real
numbers.
 THE Θ − Notation…
• f(n) is said to be Θ(g(n)) if there exists a natural
number n0 and two positive constants c1and c2 such
that.

∀n ≥ n0, c1g(n) ≤ f(n) ≤ c2g(n)

Consequently, if lim f(n)/g(n) exists, then

n→∞

f(n)
lim = c implies f(n) = Θ(g(n)),
n→∞ g(n)

where c is a constant strictly greater than 0.

 THE Θ − Notation…
• An important consequence of the above definition is that.

• f(n) = Θ(g(n)) iff f(n) = O(g(n)) and

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

• Unlike the previous two notations, the Θ − notation

gives an exact picture of the rate of growth of the
running time of an algorithm.

• Thus, the running time of some algorithms as

INSERTIONSORT cannot be expressed using this notation,
as the running time ranges from linear to quadratic.
 THE Θ − Notation…
• On the other hand, the running time of some
algorithms like Algorithm SELECTIONSORT and
Algorithm BOTTOMUPSORT can be described precisely
using this notation.

• It may be helpful to think of O as similar to ≤, Ω as

similar to≥ and Θ as similar to =.

• We emphasized the phrase “similar to” since one

should be cautious not to confuse the exact relations
with the asymptotic notations.
 THE Θ − Notation…
• For example 100n = O(n) although 100n ≥ n,

• n = Ω(100n) although n ≤ 100n and

• n = Θ(100n) although n ≠ 100n.

Example 1.5 : Let f(n) = 10n 2 + 20n.

2 2
• Then, f(n) = O(n ) , since for all n ≥ 1, f(n) ≤ 30n .

2 2
• f(n) = Ω(n ) since ∀ n ≥ 1, f(n) ≥ n .
2 2 2
• Also, f(n) = Θ(n ) since ∀ n ≥ 1,n ≤ f(n) ≤ 30n .
 THE Θ − Notation…
• We can also establish these three relations using the
limits as mentioned above.

Since lim (10n 2 + 20)/n 2 = 10, we see that

n→∞

f(n) = O(n 2), f(n) = Ω(n 2) and f(n) = Θ(n 2).

THE O − Notation
NEXT LECTURE

53
 END OF

WEEK THREE

54