add notes on efficiency

1 files changed, 13 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 6e1bcfe..2997cf6 100644
--- a/notes.md
+++ b/notes.md
@@ -67,3 +67,16 @@ real-world setting?
       a point in time to travel that doesn't align with orbital conditions might
       make it impossible for humans to survie the trip.
     * Driving directions from point A to B.
+
+# Efficiency
+
+Different algorithms devised to solve the same problem often differ dramatically
+in their efficiency.
+
+* insertion sort takes n time to sort n items.
+* merge sort takes time roughly equal to nlg(n) time to sort n items.
+
+By using an algorithm whose running time grows more slowly, even with a poor
+compiler, computer B runes more than 17 times faster than computer A!
+
+As the problem size increases, so does the relative advantage of merge sort.