1

Lecture #10
• Big-O aka “How Fast Is that Algorithm?”
• Sorting Algorithms, part I
• Appendix - ShellSort
 Big-O
2

THE WAY THEY TEACH BIG-O

AT USC
 Big-O
What’s the big picture?
Big-O is a technique that lets you quickly
understand an algorithm’s efficiency.

“This function has a big-O of N2 which means

that if you pass in N items to it, it will take
roughly N2 steps to process its data.”

Big-O is not exact - instead, it gives rough Uses:

estimates in terms of well-known functions Picking the best
like log2(N), N, N*log2(N), or N2. algorithm (so you
don’t look bad at
We use the Big-O approach to quickly compare work), job
different algorithms and pick the best one. interviews, etc.
4

How Fast is That Algorithm?

Sometimes we want to ask “How fast is that algorithm?”

Or: “Which algorithm is

faster, A or B?”

A
B

Question: How can you measure the “speed”

of an algorithm?
5

How Fast is That Algorithm?

Right! We could measure the time it
takes for an algorithm to run.

But that has flaws!

What are they?
Carey: “My algorithm finished in 31 seconds.”
Cedric: “Mine finished in 30 seconds, it’s better!”
Carey: “Not so fast! How fast is your PC? Mine is 1GHZ.”

Cedric: “Err… Mine is 3GHZ.”

Carey: “Aha – so my algorithm is really almost 3x faster!”

Cedric: “Sigh. Carey’s right again.”

6

How Fast is That Algorithm?

Ok, so simply measuring the run-time of an
algorithm isn’t really all that useful.

What if instead we measure an algorithm based on:

how many computer instructions it takes
to solve a problem of a given size

Carey: “My algorithm took 370 million instructions

to sort 1,000 numbers.”
Cedric: “Dude – you SUCK! Mine only took only 5 million
instructions, it’s better!”
Carey: “Not so fast grasshopper! Mine might be slower on
1,000 numbers, but what if we sort 1 million numbers?”
Cedric: “Hmm. I don’t know – I haven’t tried.”
7

How Fast is That Algorithm?

So just rating an algorithm based on how many steps it
takes on a particular set of data doesn’t tell us much.

An algorithm might look efficient when applied to a small

amount of data (e.g., 1,000 numbers)

But really “blow chunks” when applied to a lot of data

(e.g. 1 billion numbers)

We’d like to understand how our algorithm

performs under all circumstances!
8

How Fast is That Algorithm?

Hmmm. What else could we do?

Right! What if we specify

the number of instructions used by an algorithm
as a function of the size of the input data.

N numbers.”
“I’m trying to sort 1000
“Algorithm A takes 5 5·N 2
million instructions to do that.”
“Algorithm B takes 307 million instructions to do that.”
37,000·N

Now we can predict which algorithm will be faster

for any value of N!
9

How Fast is That Algorithm?

“I’m trying to sort N numbers.”
“Algorithm A takes 5·N2 instructions to do that.”
“Algorithm B takes 37,000·N instructions to do that.”

Ok, what if we’re sorting 1,000 numbers:

“Algorithm A takes 5M instructions.”
“Algorithm B takes 37M instructions.”
Ok, what if we’re sorting 10,000 numbers:
“Algorithm A takes 500M instructions.”
“Algorithm B takes 370M instructions.”

Ok, what if we’re sorting 1 million numbers:

“Algorithm A takes 5 trillion instructions.”
“Algorithm B takes 37 billion instructions.”
10

How Fast is That Algorithm?

“I’m trying to sort N numbers.”
“Algorithm A takes 5·N2 instructions to do that.”
“Algorithm B takes 37,000·N instructions to do that.”

Cool! When we measure this way, we get two benefits:

1. We can compare two algorithms for a given sized input.

2. We can predict the performance of those algorithms

when they are applied to less or more data.

This is the idea behind the “Big-O” concept used in

Computer Science.

No, not Oprah. Let’s learn the details!

11

Big-O: The Concept

The Big-O approach measures an algorithm
by the gross number of steps that it requires
to process an input of size N
in the WORST CASE scenario.

We could be specific and say:

“Algorithm X requires 5N2+3N+20 steps to process N items.”

But with Big-O, we

ignore the coefficients and lower-order terms of the expression…

So we’d say:
“The Big-O of Algorithm X is N2.”

While less specific, this still gives us an overall

impression of an algorithm’s worst-case efficiency.
12

Big-O: The Concept

Big-O Idea: Use simple functions like log(n), n, n2, n log(n),
n3, etc. to convey how many operations an algorithm must
perform to process n items in the worst case.
This is pronounced:
“oh of n squared”

“That sorting algorithm is O(n2), so to sort n=1000 items it

requires roughly 1 million operations.”
“That sorting algorithm is O(n·log2n), so to sort n=1000
items requires roughly 10,000 operations.”
This allows us to easily compare two different
algorithms:

“Algorithm A is O(n2), which is much slower than

algorithm B which is O(n·log2n).”
13

Big-O
So how do we compute the Big-O of a function?

First, we need to determine the number of operations

an algorithm performs. Let’s call this f(n).

By operations, we mean any of the following:

1. Accessing an item (e.g. an item in an array)
2. Evaluating a mathematical expression
3. Traversing a single link in a linked list, etc…

Let’s see how to evaluate the number of operations for

a simple example…
14

Big-O – How to Compute f(n)

Compute f(n), the # of
int arr[n][n]; critical operations, that this
for ( int i = 0; i < n; i++ ) algorithm performs?
for ( int j = 0; j < n; j++ )
arr[i][j] = 0; f(n) = 1+ n + n + n + n2 + n2 + n2
f(n) = 3n2 +3n + 1
1. Our algorithm initializes the value of i once.
2. Our algorithm performs n comparisons between i and n.
3. Our algorithm increments the variable i, n times.
4. Our algorithm initializes the value of j, n different times.
5. Our algorithm performs n2 comparisons between j and n.
6. Our algorithm increments the variable j, n2 times.
7. Our algorithm sets arr[i][j]’s value n2 times.

Now that we have f(n), we can compute our algorithm’s Big-O.

15

Big-O – The Complete Approach

Here are the steps to compute the Big-O of an algorithm:

1. Determine how many steps f(n) an algorithm requires

to solve a problem, in terms of the number of items n.
2. Keep the most significant term of that function and
throw away the rest. For example:
a. f(n) = 3n2+3n+1 becomes f(n) = 3n2
b. f(n) = 2n log(n) + 3n becomes f(n) = 2n log(n)
3. Now remove any constant multiplier from the function:
a. f(n) = 3n2 becomes f(n) = n2
b. f(n) = 2n log(n) becomes f(n) = n log(n)
4. This gives you your “big oh”:
a. f(n) = 3n2+3n+1 is therefore O(n2)
b. f(n) = 2n log(n) + 3n is therefore O(n log(n))
16

Big-O Simplification
Actually, if you think about it, there’s no need to compute
the exact f(n) of an algorithm…

Why? Because we end up throwing away all of the lower-

order terms and coefficients anyway!

All you need to do is focus on the most frequently

occurring operation(s) to save time!

int arr[n][n];
for ( int i = 0; i < n; i++ ) f(n) = n2
for ( int j = 0; j < n; j++ ) Our algorithm is O(n2).
arr[i][j] = 0;
17

Big-O
So if I say: “This algorithm is O(n2).”
I really mean: “To process n items, this algorithm requires
roughly n2 operations.”

By using only the most

4000

significant term
3500

3000
(e.g. n2 from 2n2+3n+1) Number of operations
2500

We can quickly obtain a 2000

rough approximation 1500

1000

of how many steps our

f(n)=n
500

algorithm will take 0

1 10 20 30 40 50 60 70 80 90 100 110

to process n items. Number of items, n

18

Big-O Complexity
log2n N nlog2n n2 n3 2n

3 10 30 100 1000 1000

6 100 600 10,000 1,000,000 1030

9 1,000 9,000 1,000,000 1,000,000,000 10301

13 10,000 130,000 100,000,000 1012 WOW!

16 100,000 1,600,000 1010 1015 WOW!

19 1,000,000 19,000,000 1012 1018 WOW!

What if you wanted to use an O(n3) algorithm to sort a

million numbers? Your algorithm would require roughly
1,000,000,000,000,000,000 steps!
But an O(n log2(n)) algorithm would use only 19,000,000 steps!
19

Big-O Complexity
1,000,000,000,000,000,000 vs 19,000,000!

GREAT PROGRAMMERS know that the choice of

algorithm makes all the difference in the world.

NOT-SO-GREAT programmers think that you can tweak a

poor algorithm to make it better!

Say you improve an O(n3) algorithm from f(n) = 5n3 steps to f(n) = 1.5n3
steps. For n=1,000,000, that reduces the number of steps from
5,000,000,000,000,000,000 to 1,500,000,000,000,000,000.
(Big deal… so it’ll take 1.5 years to run instead of 5 years)

However, if you can find an algorithm that’s O(n·log n) steps, say

f(n) = 10·n log n, you can solve the problem in 190,000,000 steps.
(Which will take just a few seconds or less on a modern PC!)
20

Don’t be a Big-O NUT!

When you’re writing a program that operates on a large
number of items, evaluating Big-O is key. It can mean the
difference between a usable program and an unusable one.
But what if you have a small number of items, e.g. n<50?

In this case, all of your 4000

algorithms require only a 3500

small number of steps. Number of operations

3000

2500

In such situations (when 2000

you know n is small), 1500

forget which Big-O is 1000

better and choose the 500

f(n)=n
easiest-to-program 0
1 10 20 30 40 50 60 70 80 90 100 110
algorithm. It’ll save you Number of items, n

lots of headaches.
21

Don’t be a Big-O NUT!

When you’re writing a program that operates on a large
number of items, evaluating Big-O is key. It can mean the
difference between a usable program and an unusable one.
But what if you have a small number of items, e.g. n<50?

In this case, all of your 4000

algorithms require only a 3500

small number of steps. Number of operations

3000

2500

In such situations (when 2000

you know n is small), 1500

forget which Big-O is 1000

better and choose the 500

f(n)=n
easiest-to-program 0
1 10 20 30 40 50 60 70 80 90 100 110
algorithm. It’ll save you Number of items, n

lots of headaches.
 Find the Big-O Challenge, Part 1
22

for ( int i = 0; i < n; i+=2 ) for (int i=0 ; i < n ; i++)

sum++; {
int k = n;
while (k > 1)
for ( int i = 0; i < q; i++ ) {
for ( int j = 0; j < q; j++ ) sum++;
sum++; k = k/3;
}
for ( int i = 0; i < n; i++ ) }
for ( int j = 0; j < n*n; j++ ) void foo( )
sum++; {
int i, sum = 0;
k = n;
while (k > 1) for (i=0 ; i < n*n ; i++) O(N3)

{ sum += i;
O(N*log3N)

sum++;
O(log2N)
O(N3)

k = k/2; for (i=0 ; i < n*n*n ; i++) O(Q2)

O(N)
sum += i;
}
right:

}
bottom, left to
From top to
 Find the Big-O Challenge, Part 1a
23

int searchArray(int arr[], int n, int forValue)

{
for ( int i = 0; i < n; i++ )
{
if (arr[i] == forValue)
return i;
}

return -1; // not found

}

void addItemToEndOfArray(int arr[], int &n, int addMe)

{ N is.

arr[n] = addMe;
matter how large
of steps, no

n = n + 1;
constant number
one step or a

}
O(1) or O(C) – just
O(N)
bottom:
From top to
 Big-O… my
24
void mystery(int n)
{
for ( int q = 0; q < n; q++ )
Sometimes you’ll run into an algorithm {
that isn’t so clear-cut. For example, for (int x = 0 ; x < q ; x++)
what’s the Big-O of mystery? {
cout << “Waahoo!”;
}
It’s clear that the outer loop runs n }
times, but what about the inner loop? }

When q = 0, the inner loop runs 0 iterations. So what’s the Big-O?

When q = 1, the inner loop runs 1 iteration.
n 2-n
When q = 2, the inner loop runs 2 iterations.
... f(n) =
When q = n-1, the inner loop runs n-1 iterations.
2 2
O(n2)
So the cout statement will run a total of:
0 times + 1 time + 2 times + 3 times + … + n-1 times
n·(n-1)
And if you recall a clever trick, this is equal to:
2
 Big-O: Such Ugly Math! ☺
25

But we’re not Math geeks… We’re CS geeks! So here’s a

way to address these situations without formulas!
Step 1:
Locate all loops that don’t run for a fixed number of iterations and
determine the maximum number of iterations each loop could run for.
Step 2:
Turn these loops into loops with a fixed number of iterations, using
their maximum possible iteration count.
Step 3:
Finally, do your Big-O analysis.

func1(int n) int main( )

{ {
for ( int i = 0; i < n; i++ ) for ( int x = 0; x < n; x++ )
for (int j=0; j < i ;j++) for (int j=0; j < x*x ; j++)
cout << j; cout << “Burp!”;
} }

O(n2) n O(n3) n*n

 Find the Big-O Challenge, Part 2
26

for ( int j = 0; j < n; j++ ) for ( int i = 0; i < n; i++ )

for ( int k = 0; k < j; k++ ) {
sum++; Circ arr[n];
for ( int i = 0; i < q*q; i++ ) arr[i].setRadius(i);
for ( int j = 0; j < i; j++ ) }
sum++;
for (int i=0 ; i < n ; i++)
for ( int i = 0; i < n; i++ )
{
for ( int j = 0; j < i*i; j++ )
int k = i;
for ( int k = 0; k < j; k++)
while (k > 1)
sum++;
{ O(N*log2N)
times, once per item!
sum++; the constructor N

for ( int i = 0; i < p; i++ )

array of N items calls
k = k/2; that constructing an

for ( int j = 0; j < i*i; j++ )

O(N2) – don’t forget
}
for ( int k = 0; k < i; k++)
O(P4)
} O(N5)

sum++;
O(Q4)
O(N2)
left to right:
From top to bottom,
27

Big-O for Multi-input Algorithms

Often, an algorithm will The number of CS
The number of people, p, and
operate on two (or more) students, c,
the number of foods, f, are
independent data sets, each and EE students, e, are
completely independent.
of a different size. also independent.

void buffet(string people[], int p, void tinder(string csmajors[], int c,

string foods[], int f) string eemajors[], int e)
{ {
int i, j; for (int i=0; i < c ;i++)
for (int j=0; j < c ;j++)
for (i=0; i < p ;i++) cout << csmajors[i] << “ dates “
for (j=0; j < f ;j++) << csmajors[j] << endl;
cout << people[i] << “ ate “
for (int k=0; k < e ;k++)
<< foods[j] << endl;
cout << eemajors[k] << “ sits at home“;
}
}

In these cases, when we What? O(c2 + e) and not just O(c2) ?

compute the algorithm’s
Correct! Even though c2 seems
Big-O, we must to take into
bigger than e, we must include both
account both independent
independent variables in our Big-O!
sizes.
28

Big-O for Multi-input Algorithms

Why must we include both variables in the Big-O
(even if one is higher-order than the other)?

Because either variable could dominate the other!

void tinder(string csmajors[], int c, ALERT! But… don’t forget -

string eemajors[], int e) you still must eliminate lower-
{
for (int i=0; i < c ;i++)
order terms for each
for (int j=0; j < c ;j++) independent variable!
cout << csmajors[i] << “ dates “
<< csmajors[j] << endl;
void tinder(string csmajors[], int c,
string eemajors[], int e)
for (int k=0; k < e ;k++) {
cout << eemajors[k] << “ sits at home“ for (int i=0; i < c ;i++)
} for (int j=0; j < c ;j++)
cout << csmajors[i] << “ dates “
<< csmajors[j] << endl;

for (int m=0; m < c ; m++)

cout << csmajors[m] << “ is still a nerd”;

for (int k=0; k < e ;k++)

cout << eemajors[k] << “ sits at home“
}
29

Find the Big-O Challenge, Part 3

void bar( int n, int q ) void burp( int n )
{ {
for (int i=0 ; i < n*n ; i++) for (int i=0 ; i < n ; i++)
{ cout << “Muahahaha!”;
for (int j = 0; j < q; j++)
cout << “I love CS!”; for (int i=0 ; i < n*n ; i++)
} cout << “Vomit!”;
} }

void bletch( int n, int q ) void barf( int n, int q )

{ {

for (int i=0 ; i < n ; i++) for (int i=0 ; i < n ; i++)
{
cout << “Muahahaha!”; if (i == n/2)
{
for (int i=0 ; i < q*q ; i++) for ( int k = 0; k < q; k++ ) on all of the N items!

cout << “Vomit!”; cout << “Muahahaha!”;

not run the inner loop
is equal to n/2, we do
}
} loop just once, when i
else we only run the inner

cout << “Burp!”;

O(N + Q) – note that
O(N2)
}
} O(N + Q2)
O(N2 * Q)
left to right:
From top to bottom,
30

The STL and Big-O

Remember the STL - stacks, queues, sets, vectors, lists and maps?
Well, these classes use algorithms to get things done…
And these algorithms have Big-Os too!

void inDict(set<string> & d, string w) For example, if we want to

{ search for a word in a set that
if ( d.find(w) == d.end() ) contains n words (a dictionary),
cout << w << “ isn’t in dictionary!”;
}
it requires O( log2(n) ) steps!

void otherFunc(vector<int> & vec) But if we want to add a value

{ to the end of a vector holding
vec.push_back(42); n items, it takes just one step,
vec.erase( vec.begin() ); so it’s O( 1 )!
}

And if we want to delete the 1st value from a vector containing

n items, it takes a whopping n steps, making it O(n)!
31

Well, to search a set of The STL and Big-O

n items for a single value
requires log2(n) steps…
And we repeat this
search operation D
different times…

It’s important to understand the Big-O

of each operation
(e.g. push_back, erase) for each STL
class (e.g., list, vector)… void inDict(set<string> & d, string w)
… because without knowing the Big-Os of {
the STL classes, if ( d.find(w) == d.end() )
cout << w << “ isn’t in dictionary!”;
we can’t compute the Big-O of code that
uses the STL classes!
}
For example…
If we write a loop of our own that runs D void spellCheck( set<int> &dict,
times… string doc[], int D )
And each iteration of our loop searches for {
an item in a set holding n items…
for (int i=0; i < D ; i++)
inDict( dict, doc[i] );
Then what’s the Big-O of our loop???

Then the Big-O of our whole }

loop would be O( D * log2(n) ).
32
Computing the Big-O of Algorithms that use STL
What is the Big-O of the loop in terms of q?

And as such,
Ok, our vector our loop runs
contains q values… q times… And each time our loop
runs, we:
void printNums( vector<int> & v ) 1. Access an item: the
{ cost of accessing an item
int q = v.size(); in a vector is O(1) - so
for ( int i = 0; i < q ; i++ ) we’ll remember that!
{
int a = v[0]; // get 1st item 2. Erase the first item in the
vector: the Big-O of erasing the
cout << a; // print it out
first item in a vector with q items
v.erase( v.begin() ); // erase 1st is O(q).
item
v.push_back(a); // add it to 3. Add the item to the end of the
end vector: the Big-O of adding an item
}
to the end of a vector is O(1).
} Hint:
The STL vector
Total steps performed during our loop:
Insert at the top/middle: O(n)
q * (1 + q + 1 ) Insert an the end: O(1)
Delete an item from top/middle: O(n)
So our total Big-O is: Delete an item from the end: O(1)
Access an item: O(1)
O(q2)
Finding an item: O(n)
33

STL and Big Oh Cheat Sheet

When describing the Big-O of each operation (e.g. insert) on a container (e.g., a vector)
below, we assume that the container holds n items when the operation is performed.
Name: list Name: vector
Purpose: Linked list Purpose: A resizable array
Usage: list<int> x; x.push_back(5); Usage: vector<int> v; v.push_back(42);
Inserting an item (top, middle*, or bottom): O(1) Inserting an item (top, or middle): O(n)
Deleting an item (top, middle*, or bottom): O(1) Inserting an item (bottom): O(1)
Accessing an item (top or bottom): O(1) Deleting an item (top, or middle): O(n)
Accessing an item (middle): O(n) Deleting an item (bottom): O(1)
Finding an item: O(n) Accessing an item (top, middle, or bottom): O(1)
*But to get to the middle, you may have to Finding an item: O(n)
first iterate through X items, at cost O(x)

Name: set Name: map

Purpose: Maintains a set of unique items Purpose: Maps one item to another
Usage: set<string> s; s.insert(“Ack!”); Usage: map<int,string> m; m[10] = “Bill”;
Inserting a new item: O(log2n) Inserting a new item: O(log2n)
Finding an item: O(log2n) Finding an item: O(log2n)
Deleting an item: O(log2n) Deleting an item: O(log2n)

Name: queue and stack

Purpose: Classic stack/queue If instead of holding n items, a container holds
Usage: queue<long> q; q.push(5);
Inserting a new item: O(1)
p items, then just replace “n” with “p” when you
Popping an item: O(1) do your analysis.
Examining the top: O(1)
 Computing the Big-O of Algorithms that use STL
34

When evaluating STL-based algorithms, first determine the

maximum # of items each container could possibly hold..
Then do your Big-O analysis under the assumption that Ok. Well, after the loop
each container always holds exactly this number of items. finishes, our set will hold
q values…
Ok, I’ll assume that our set always has q This is the maximum # of
items in it. That means that each time values it can hold.
we insert an item into our set it takes
log2(q) steps.
So if our loop runs a total of
q iterations… and each
int main( ) iteration we insert at a cost
of log2(q) into our set… Then
{ our total cost is q * log2(q)
set< int > nums;
for (int i=0; i < q ; i ++)
nums.insert( i );
}

And that’s the correct

The STL set
answer! Inserting a new item: O(log2n)
Finding an item: O(log2n)
Deleting an item: O(log2n)
35

Find the Big-O Challenge, Part 4

See if you can figure out the Big-O of these
functions which use the STL!

Well, assuming our // Assume p items in vector v So there are p total

vector has p items void clearFromFront(vector<int> &v) loop iterations, and
and we delete one { during each iteration,
item per iteration, while ( v.size() > 0 ) we perform p steps to
our loop runs for p { delete the first item:
steps. v.erase( v.begin() ); // erase 1st item O(p2)
}
}

Hints: During each step, we delete the

vector’s first item.
The STL vector The STL set
Let’s assume the vector always
Insert at the top/middle: O(n) Inserting a new item: O(log n)
has p items, no matter what. 2
Insert an the end: O(1) Finding an item: O(log2n)
Delete an item from top/middle: O(n) Cost of deleting
Deleting an item: first item: O(p) n)
O(log 2
Delete an item from the end: O(1)
Access an item: O(1)
Finding an item: O(n)
36
So we perform q2 total loop
Find the Big-O Challenge, Part 4
iterations, and during each
iteration, we perform log2(q2)
steps to See ifan
insert you can figure out the Big-O of these
item:
functions which use the STL!
O(q2*log2(q2))

// Assume s starts out empty Ok, our loop runs

void addItems(set<int> &s, int q) through q2 total
{ iterations.
for (int i=0; i < q*q; i++)
s.insert(i);
} And the cost of adding a
single item to a set with q
2
As before, to compute the cost of
items is… O(log2(q2))
an STL operation, we assume theHints:
set always holds itsvector
The STL max # of items. The STL set
Insert
In thisatcase,
the top/middle: O(n)
the set will eventually Inserting a new item: O(log2n)
Insert
holdanq2the end:– that’s our max!
items O(1) Finding an item: O(log2n)
Delete an item from top/middle: O(n) Deleting an item: O(log2n)
Delete an item from the end: O(1)
Access an item: O(1)
Finding an item: O(n)
37

Find the Big-O Challenge,

Well, assuming our Part 4
So there are z total loop
iterations, and during each
vector has z items
See
and we delete one if you can figure out the iteration,
Big-O of we perform 1 step
these
item per iteration,
our loop runs for z
functions which use theto delete the last item:
STL!
O(z)
steps.
// Assume z items in vector v
void clearFromBack(vector<int> &v)
{
while ( v.size() > 0 )
{
v.pop_back(); // erase last item
}
}

Hints:
The STL vector During eachTheiteration,
STL set we delete
Insert at the top/middle: O(n) the
Inserting vector’s
a new item: last item.
O(log2n)
Insert an the end: O(1) Finding an item: O(log2n)
Delete an item from top/middle: O(n) Let’s assume
Deleting the vector always
an item: O(loghas
2n)
z
Delete an item from the end: O(1) items, no matter what.
Access an item: O(1)
Finding an item: O(n) Cost of deleting last item: O(1)
 Find the Big-O Challenge, Part 5
38

Q
{1,9,…} I have a vector of sets of ints:
{2,3,…}
vector< set<int> > v;
{-7, 8,…}
N You may assume vector v has N total sets in it.
{4,5,8,…}
You may assume that each set has an avg of Q items.
{}
{-1,0,1,…} Questions:
#1 What is the Big-O of determining if the first set, v[0],
contains the value 7?
#2 What is the Big-O of determining if any set in v has a value of 7?

#3 What is the Big-O of determining the number of even values in all of v?

#4 What is the Big-O of finding the first set with a value of 7 and then counting
the number of even values in that set?

#4 N*log2(Q) + Q The STL set

#3 N*Q Inserting a new item: O(log2n)
#2 N*log2(Q) Finding an item: O(log2n)
#1 log2(Q) Deleting an item: O(log2n)
39
Space Complexity
Space complexity is the big-o of how much storage your
algorithm uses, as a function of the data input size, n.

void reverse(int array[], int n) void reverse(int array[], int n)

{ {
Uses just 2 new variables, no
int tmp, i; matter how big the array is! int *tmparr = new int[n];

for (i = 0; i < n/2; ++i) for (int i = 0; i < n; ++i)

{ tmparr[n-i-1] = array[i];
tmp = array[i]; for (int i = 0; i < n; ++i)
array[i] = array[n-i-1]; array[i] = tmparr[i];
array[n-i-1] = tmp;
} delete [] tmparr;
} }

Space Complexity: Space Complexity:

O(1) or O(constant) O(n)
 Space Complexity
40 This function uses just
two 4-byte memory
slots no matter how
big n is. Be careful – space
Space Complexity: // prints from n down-to 0
complexity can be // with recursion!
O(1)
tricky with recursion! // prints from n down-to 0
n 1000 i // void
withprintNums(int
recursion! n)
{
// prints from n down-to 0
n 997 void
// with if printNums(int
recursion! n)
// prints from n down-to 0 (n <n0) return;0
{
// prints from down-to
// without recursion!
n 998 //void
withprintNums(int
recursion!
cout << n <<
if (n < 0) return;
n)
“\n”;
void printNums(int n) { printNums(n-1);
void printNums(int n)
{ n 999 cout << n <<
if} (n < 0) return; “\n”;
{
printNums(n-1);
int i;
n 1000 } cout
if (n < 0)<< nreturn;
<< “\n”;
for (i=n; i >= 0; i--) printNums(n-1);
cout << i << “\n”; } cout << n << “\n”;
printNums(n-1);
} }
The recursive version
creates a whole new
int main() variable for each of the int main()
n levels of recursion!
{ {
printNums(1000); Space Complexity: O(n) printNums(1000);
} }
 Inefficient Sorting Algos.
41
 Inefficient Sorting Algorithms
What’s the big picture?
Sorting is the process of ordering a bunch of
values, e.g., from smallest to largest.

There are a handful of “inefficient”

algorithms to do sorting, like selection sort,
insertion sort and bubble sort.

These algorithms generally require O(N2)

steps to order N values. They’re suuuper slow.
Uses:
Why slow? They compare every item to every Only CS32 exams
other item, swapping out-of-order items. and some job
interviews.
 Sorting!
43

Sorting is the process of ordering a bunch of items based

on one or more rules, subject to one or more constraints…

Items – what are we sorting,

and how many are there?
• Strings, numbers, student records,
C++ objects (e.g., Circles, Robots)
• Thousands, millions or trillions?

Rules – how do we order them?

• Ascending vs. Descending order
• Based on Circle radius? Student GPA?
• Based on multiple criteria, e.g.:
by last name, then first name

Constraints?
• Are the items in RAM or on disk?
• Is the data in an array or a linked list?
 Carey’s 2 Rules
44

of Sorting

Rule #1:
Don’t choose a sorting algorithm until you
understand the requirements of your problem.

Rule #2:
Always choose the simplest sorting algorithm
possible that meets your requirements.
45

The Selection Sort

– Look at all N books, select the
shortest book
– Swap this with the first book
– Look at the remaining N-1
books, and select the shortest
– Swap this book with the
second book
– Look at the remaining N-2
books, and select the shortest
– Swap this book with the So, is our sort efficient?
third book and so on…
If we have N books, how many
steps does it take to sort them?

Let’s assume a step is any time we

either swap a book or
point our finger at a book.
 46

The Selection Sort- Speed

– Look at all N books, select the N steps
shortest book
1 step – Swap this with the first book
– Look at the remaining N-1 N-1 steps
books, and select the shortest
1 step – Swap this book with the
second book
– Look at the remaining N-2 N-2 steps
books, and select the shortest
1 step – Swap this book with the Now if you remember your
So, is our sort math…
efficient?
third book and so on…
(and
If so
weon)
have N
N +books, how
N-1 + N-2 + …many
+2+1
(and so on) steps does it takeisto sort
equal to...them?
So this comes to:
N * (N+1)
N swap steps Let’s assume a step is2 any time we
PLUS either swap
So Selection a isbook
Sort O(N2),oror, for N
N + N-1 + N-2 + … + 2 + 1 point ouryou
books, finger at a Nbook.
need roughly 2 steps to
steps to find the smallest item sort them.
47

Selection Sort – Better or Worse?

Are there any kinds of input data where Selection
Sort is either more or less efficient?

For example, what if all of the

books are mostly in order
before our sort starts?

void selectSort(shelf of N books)

{
for i = 1 to N
{
find the smallest book
between slots i and N
swap this smallest book
with book i; No! Selection sort
} takes just as many
} steps either way!
 The Selection
SelectionSort
48
Sort Questions
Can Selection Sort be applied easily to
And here’s the C++ sort items within a linked list?
source code to sort a
Is Selection Sort “stable” or “unstable”?
bunch of numbers…

void selectionSort(int A[], int n)

{
for (int i = 0; i < n; i++)
{ }-
For each of the n array
elements…

}
int minIndex = i;
for (int j = i+1; j < n; j++) Locate the smallest item
{
if (A[j] < A[minIndex]) -
in the array between the
ith slot and slot n-1.
minIndex = j;
}

}
swap(A[i], A[minIndex]); }-
Swap the smallest item
found with slot A[i].
}
 What’s a Stable Sort?
49

Imagine that N old people line up to buy laxatives at a drugstore.

And the drugstore wants to sort them and serve them based on urgency.

The drugstore needs to pick a sort algorithm to re-order the guests.

They can choose between a “stable” sort or an “unstable” sort.
An “unstable” sorting algorithm re-orders the items without taking into account their
initial ordering.
A “stable” sorting algorithm does take into account the initial
ordering when sorting, maintaining the order of similar-valued items.
As you solve problems (in class or at work) you should choose
your sort depending on whether stability is important.
If you forget the concept, just remember the laxatives! ☺

People in line Unstable Sort Results Stable Sort Results

Ebeneezer - 8 days Steve – 8 days Ebeneezer - 8 days
Carey – 5 days Vicki – 8 days Steve – 8 days
David – 2 days Ebeneezer - 8 days Vicki – 8 days
Michael – 4 days Andrea – 5 days Carey – 5 days
Steve – 8 days Carey – 5 days Andrea – 5 days
Vicki – 8 days Michael – 4 days Michael – 4 days
Andrea – 5 days David – 2 days David – 2 days
 The Selection
SelectionSort
50
Sort Questions
Can Selection Sort be applied easily to
And here’s the C++ source sort items within a linked list?
code to sort a bunch of Is Selection Sort “stable” or “unstable”?
numbers…
When might you use Selection Sort?

void selectionSort(int A[], int n)

{ Here’s a hint – consider
for (int i = 0; i < n; i++) this array:
{ 10 10 1
int minIndex = i;
for (int j = i+1; j < n; j++) When Selection Sort
{ finds the 1, it swaps it
if (A[j] < A[minIndex]) with the first 10.
minIndex = j;
} Then our array ends up
swap(A[i], A[minIndex]); like this:
}
} 1 10 10
51

The Insertion Sort

Well, we couldn’t just teach
you one sort, right?

Let’s learn another!

The insertion sort is probably the

most common way…

to sort playing cards!

(But I’ll still explain the sort with

library books)
 The Insertion Sort
52

Let’s focus on the first two

books – ignore the rest.
• If the last book in this set is
in the wrong order
• Remove it from the shelf
• Shift the book before it
to the right
• Insert our book into the
proper slot

Great! Now our first two

books are in sorted order
(ignoring the others)
 The Insertion Sort
53

Ok, now focus on the first

three books – ignore the rest.
• If the last book in this set is
in the wrong order
• Remove it from the shelf
• Shift the books before it
to the right, as necessary
?
• Insert our book into the
proper slot

Great! Now our first three

books are in sorted order
(ignoring the others)
 The Insertion Sort
54

Ok, now focus on the first

four books – ignore the rest.
• If the last book in this set is
in the wrong order
• Remove it from the shelf
• Shift the books before it
to the right, as necessary
?
• Insert our book into the
proper slot

Great! Now our first four

books are in sorted order!

We just keep repeating this

process until the entire shelf
is sorted!
 The Insertion Sort
55

So what’s the complete algorithm?

Start with set size s = 2

While there are still books to sort:

• Focus on the first s books
• If the last book in this set is
in the wrong order
• Remove it from the shelf
• Shift the books before it
to the right, as necessary
• Insert our book into the
proper slot
•s=s+1
 The Insertion Sort - Speed
56

So what’s the Big-O of our Insertion Sort?

During each round of the algorithm

we consider a larger set of books.

During the first round, we may need to

shift up to one book to find the right spot.
1 step in round 1
During the second round, we may need to

…
+ 2 steps in round 2
shift up to two books to find the right spot.
+…
+ N-1 steps in last rnd
During the last round, we may need to = roughly N2 steps
shift up to N-1 books to find the right spot.

Thus, Insertion Sort

is O(N2), and is
generally quite slow!
57

Insertion Sort – Better or Worse?

Are there any kinds of
input data where
Insertion Sort is either
more or less efficient?

Any ideas?

Right! If all books are

in the proper order…

then Insertion Sort Conversely, a perfectly

never needs to do any shifting! mis-ordered set of books
is the worst case.
In this case, it just takes roughly
Since every round
~N steps to sort the array! O(N) requires the
maximum shifts!
 The Insertion Sort
58
Insertion Sort Questions
Can Insertion Sort be applied easily to
sort items within a linked list?
And here’s the C++ version Is Insertion Sort a “stable” sort?
which sorts an array in When might you use Insertion Sort?
ascending order!
Focus on successively larger
void insertionSort(int A[], int n)
{
prefixes of the array. Start
for(int s = 2; s <= n; s++) with the first s=2 elements,
{ then the first s=3 elements...
int sortMe = A[ s - 1 ]; Make a copy of the last val in the
current set – this opens up a slot
int i = s - 2; in the array for us to shift items!
while (i >= 0 && sortMe < A[i]) Shift the values in the focus
{
region right until we find the
A[i+1] = A[i];
proper slot for sortMe.
--i;
}
Store the sortMe value into the
A[i+1] = sortMe; vacated slot.
}
}
59

Everyone loves to Sort But it’s actually

quite simple… And
make fun of the: sometimes simple
is good!

Ok, what’s the algorithm?

Start at the top element of your array

Compare the first two elements: A[0] and A[1]
If they’re out of order, then swap them
Then advance one element in your array
Compare these two elements: A[1] and A[2]
If they’re out of order, swap them
...
Repeat this process of comparing A[j] with A[j+1] and swapping if they’re
out of order until you hit the end of the array

When you hit the end of the array, if you made at least one swap on your
way down, then start back at the top and repeat the whole process again!
60

Bubble Sort In Action!

Let’s see how bubble sort works with

?
SWAP? some of the hottest peppers…
…to sort them from least
spicy to most spicy!

Compare the first two elements

If they’re out of order, then swap them

Compare the next two elements: A[1] and A[2]

If they’re out of order, swap them

Compare the final two elements: A[2] and A[3]

If they’re out of order, swap them

When you hit the end, if you made at least one

swap, then repeat the whole process again!
 Bubble Sort Speed
61

Ok, so Bubble Sort

has a bad wrap.
During each pass, we compare every element
Question: with its successor (and possibly swap each).
How fast is it?
That requires about N steps.

If we did even one swap, we need to repeat

Just like the whole process again from the top.
Insertion
Sort, What’s the worst case? How many times
Bubble Sort might we have to repeat the process?
is really
efficient on Right! We might have to repeat this
pre-sorted entire process N times.
arrays and
linked lists! N passes of N “bubbles” = N2

Ok, so Bubble Sort is O(N2)…

But can it ever run faster in certain cases?
62

The Bubble Sort

Bubble Sort Questions
Can Bubble Sort be applied easily to sort items
within a linked list?
Is Bubble Sort a “stable” sort?
void bubbleSort(int Arr[], int n) Is Bubble Sort ever faster than O(n2)?
When might you use
{ Bubble Sort?
bool atLeastOneSwap;

do Start by assuming
that we won’t
{
do any swaps
atLeastOneSwap = false;
for (int j = 0; j < (n-1); j++)
{ Compare each element
if (Arr[j] > Arr[j + 1]) with its neighbor and
{ swap them if they’re
Swap(Arr[j],Arr[j+1]); out-of-order.
atLeastOneSwap = true;
Don’t forget-we swapped!
}
}
} If we swapped at least
while (atLeastOneSwap == true); once, then start back at
} the top and repeat the
whole process.
63
selectionSort
Sorting Challenge For each of the N books
Find the smallest book between
slots i and N
Consider the following array
Swap this smallest book with
of integers: book i
By one round, I
mean one full trip insertionSort
through the sort’s 2 5 9 14 7 3 s=2
while/for loop. While books need sorting:
Focus on the first s books
If the last book in set is in the
which has been sorted by wrong order THEN
one round of either selection A. Remove it from shelf
sort, insertion sort or bubble B. Shift the books to
sort. the right as required
C. Insert our book into the
proper slot
Which of these sorts could NOT s=s+1
have been used on this array? bubbleSort
Why? while the shelf isn’t sorted
repeatedly swap adjacent books
if they’re out of order
64

Appendix

• Shellsort – this won’t be on your exam

65

The sort Errr….

“I want h=3”
Shellsort is based on an underlying procedure
called h-sorting. Let’s learn h-sorting first…

The method for h-sorting an array is simple:

Pick a value of h
For each element in the array:
• If A[i] and A[i+h] are out of order then
• Swap the two elements
If you swapped any elements during the last pass,
then repeat the entire process again (same h value).
66

The Shellsort: h-sorting

Pick a value of h
For each element in the array: Let’s 3-sort this array so
the shells are ascending.
• If A[i] and A[i+h] are out of order
e.g., h=3
• Swap the two elements
If you swapped any elements,
repeat the entire process again.
i i+3

SWAP?
67

The Shellsort: h-sorting

Pick a value of h
For each element in the array: Let’s 3-sort this array so
the shells are ascending.
• If A[i] and A[i+h] are out of order
e.g., h=3
• Swap the two elements
If you swapped any elements,
repeat the entire process again.
i i+3

SWAP?
68

The Shellsort:
This time we had no swaps! h-sorting
Our of
Pick a value array
h is now 3-sorted!
For each element in the array: Let’s 3-sort this array so
This means that every element
the shells are ascending.
• If A[i] and A[i+h] are
is smaller thanout of order
e.g., h=3
• Swap the two
the element elements
3 items later
If you swappedinany theelements,
array.
repeat the entire it’s
Of course, process again.
not completely Question:
sorted
i yet, just 3-sorted!
i+3 If you 1-sort an array,
which other sort
algorithm does this
remind you of?
SWAP?
69

The Shellsort It’s required

to always end
The overall Shellsort works as follows:e.g.with h=1!
5, 3, 1 or
10, 7, 4, 1
Step 1:
Select a sequence of decreasing h-values,
ending with an h-value of 1: e.g. 8,4,2,1.

Step 2:
First completely 8-sort the array…
Then completely 4-sort the array…
Then completely 2-sort the array…
Finally, completely bubble
1-sortsort the array…
and the array’s now fully sorted!

Each h-sort more correctly sorts the array, making

the process simpler each iteration.
70

Shell Sort Questions

Can Shell Sort be applied easily to

sort items within a linked list?

Is Shell Sort a “stable” sort?

What’s the Big-O of Shell Sort?

When might you use Shell Sort?

71

The Shellsort
Let’s do an example on the board:

Shellsort the following array using h values of: 3, 2, and 1.

9 5 2 14 3 7
72
selectionSort
Sorting Challenge For each of the N books
Find the smallest book between
slots i and N
Given the following numbers, Swap this smallest book with
book i
show what they would look
like after one, two and three insertionSort
outer-loop iterations of s=2
While books need sorting:
selection sort, insertion sort Focus on the first s books
and bubble sort: If the last book in set is in the
wrong order THEN
A. Remove it from shelf
9 5 2 14 3 7 B. Shift the books to
the right as required
C. Insert our book into the
proper slot
s=s+1

bubbleSort
while the shelf isn’t sorted
repeatedly swap adjacent books
if they’re out of order