Add complexity bound on binary search methods (#239)
Closes #237
In each of the list extensions that mention "Uses binary search" add a
sentence documenting that the search takes `log(n)` comparisons.
Add a sentence about using binary search and the runtime to the top
level algorithm methods.
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 6161476..806a8b0 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,5 @@
+## 1.16.1-dev
+
## 1.16.0
* Add an `Iterable.slices` extension method.
diff --git a/lib/src/algorithms.dart b/lib/src/algorithms.dart
index 820d32b..eb9e1de 100644
--- a/lib/src/algorithms.dart
+++ b/lib/src/algorithms.dart
@@ -57,6 +57,8 @@
/// Returns the first position in [sortedList] that does not compare less than
/// [value].
///
+/// Uses binary search to find the location of [value].
+/// This takes on the order of `log(n)` comparisons.
/// If the list isn't sorted according to the [compare] function, the result
/// is unpredictable.
///
@@ -72,6 +74,8 @@
/// Returns the first position in [sortedList] that is not before [value].
///
+/// Uses binary search to find the location of [value].
+/// This takes on the order of `log(n)` comparisons.
/// Elements are compared using the [compare] function of the [keyOf] property of
/// the elements.
/// If the list isn't sorted according to this order, the result is unpredictable.
diff --git a/lib/src/list_extensions.dart b/lib/src/list_extensions.dart
index 43d1ef3..4d6ae3f 100644
--- a/lib/src/list_extensions.dart
+++ b/lib/src/list_extensions.dart
@@ -16,6 +16,7 @@
/// Returns the index of [element] in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare],
/// otherwise the result is unspecified
///
@@ -26,6 +27,7 @@
/// Returns the index of [element] in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare] on the [keyOf] of elements,
/// otherwise the result is unspecified.
///
@@ -42,6 +44,7 @@
/// Returns the index of [element] in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to the natural ordering of
/// the [keyOf] of elements, otherwise the result is unspecified.
///
@@ -57,6 +60,7 @@
/// Returns the index where [element] should be in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare],
/// otherwise the result is unspecified.
///
@@ -71,6 +75,7 @@
/// Returns the index where [element] should be in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare] of
/// the [keyOf] of the elements, otherwise the result is unspecified.
///
@@ -90,6 +95,7 @@
/// Returns the index where [element] should be in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to the
/// natural ordering of the [keyOf] of the elements,
/// otherwise the result is unspecified.
@@ -276,6 +282,7 @@
/// Returns the index of [element] in this sorted list.
///
/// Uses binary search to find the location of [element].
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare],
/// otherwise the result is unspecified.
/// If [compare] is omitted, it uses the natural order of the elements.
@@ -288,6 +295,7 @@
/// Returns the index where [element] should be in this sorted list.
///
/// Uses binary search to find the location of where [element] should be.
+ /// This takes on the order of `log(n)` comparisons.
/// The list *must* be sorted according to [compare],
/// otherwise the result is unspecified.
/// If [compare] is omitted, it uses the natural order of the elements.
diff --git a/pubspec.yaml b/pubspec.yaml
index ae623b8..436a1e1 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.16.0
+version: 1.16.1-dev
description: Collections and utilities functions and classes related to collections.
repository: https://github.com/dart-lang/collection
