From dfce7a44a8135ae1f17a4a7ca7145fafc7e027a4 Mon Sep 17 00:00:00 2001 From: mo khan Date: Mon, 6 Sep 2021 17:45:02 -0600 Subject: add notes on efficiency --- notes.md | 13 +++++++++++++ 1 file changed, 13 insertions(+) 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. -- cgit v1.2.3