Skip to Main Content
Think Complexity
book

Think Complexity

by Allen B. Downey
March 2012
Beginner content levelBeginner
160 pages
4h 6m
English
O'Reilly Media, Inc.
Content preview from Think Complexity

Chapter 4. Small World Graphs

Analysis of Graph Algorithms

The order of growth for a graph algorithm is usually expressed as a function of , the number of vertices, and , the number of edges.

The order of growth for BFS is , which is a convenient way to say that the runtime grows in proportion to either or , whichever is “bigger.”

To see why, think about these four operations:

Adding a vertex to the queue

This happens once for each vertex, so the total cost is in .

Removing a vertex from the queue

This happens once for each vertex, so the total cost is in .

Marking a vertex “visited”

This happens once for each vertex, so the total cost is in .

Checking whether a vertex is marked

This happens once each edge, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Unikernels

Unikernels

Russell Pavlicek
Elemental Design Patterns

Elemental Design Patterns

Jason McColm Smith
LEGO® with Dad

LEGO® with Dad

Warren Nash

Publisher Resources

ISBN: 9781449331672Errata