315 Structure Performance Summary

This page will be devoted to summarizing our performance discussions. Below, we have included a graph for a frame of reference for the various functions.

Generic Trees

In the following, $n$ denotes the number of nodes in the tree.

Insert: 1 if we have the parent but $n$ if we have to find the parent
Access: 1 if we want to access the root but $n$ otherwise
Find: $n$
Delete: $n$ if we have to find the parent
Memory: $n$

Tries

In the following, $m$ denotes the length of a word and $n$ denotes the number of words in the trie.

Insert: $m$
Access: $m$
Find: $m$
Delete: $m$
Memory: $n\times m$

Binary Trees

In the following, $n$ denotes the number of nodes in the tree.

Insert: $log_2(n)$ when balanced but $n$ otherwise
Access: $log_2(n)$ when balanced but $n$ otherwise
Find: $log_2(n)$ when balanced but $n$ otherwise
Delete: $log_2(n)$ when balanced but $n$ otherwise
Memory: $n$

Matrix Graph

In the following, $n$ denotes the number of nodes in the graph.

Insert Node: $n$
Access Node: 1
Find Node: $n$
Delete Node: $n$
Insert Edge: 1
Access Edge: 1
Find Neighbors: $n$
Delete Edge: 1
Memory: $n^2$

List Graph

In the following, $n$ denotes the number of nodes in the graph and $e$ denotes the number of edges.

Insert Node: $n$
Access Node: 1
Find Node: $n$
Delete Node: $n$
Insert Edge: $n$
Access Edge: $n$
Find Neighbors: 1
Delete Edge: $n$
Memory: $n+e$

Priority Queue

In the following, $n$ denotes the number of elements in the priority queue.

Insert: $log_2(n)$
Access Minimum: 1
Find: $n$
Remove Minimum: $log_2(n)$
Heapify: $n$
Memory: $n$