Errata for Data Structures & Algorithms in Dart 1st Edition

Creating this topic to catch any typos and bugs in the 1st Edition of Data Structures & Algorithms in Dart.

1 Like

Hello, I think the logarithmic time complexity in chapter has a bug,
only the first operation is O(log n) the rest on O(n).
here the code from the book:

bool betterNaiveContains(int value, List<int> list) {
  if (list.isEmpty) return false;
  final middleIndex = list.length ~/ 2;

  if (value > list[middleIndex]) {
    for (var i = middleIndex; i < list.length; i++) {
      if (list[i] == value) return true;
    }
  } else {
    for (var i = middleIndex; i >= 0; i--) {
      if (list[i] == value) return true;
    }
  }

  return false;
}

This is my test case:

void main() {
  var numbers = <int>[];
  var i = 1;
  while (i < 101) {
    numbers.add(i);
    i++;
  }
  print(betterNaiveContains(100, numbers));
}

It first set the middleIndex variable to 50 which is O(log n) and in the loop just increment the middleIndex by 1 e.g 51, 52, 53… 100 which O(n) .I was expecting the middleIndex variable get divide by two each time we loop through which we get something like this 50 75, 88 ,94 97 99 and then we get 100 which will result to O(log n) I think. Anyway I new to this topic so hoping someone will help me with my expectation can’t still figure it out!

Good job on thinking algorithmically! You’re right that only the first check cuts the list in half and after that the algorithm is O(n). This results in the entire function being O(n). The O(log n) version of this algorithm isn’t presented until Chapter 12.

The original idea with this example was to gently ease readers into the notion of logarithmic time by showing how you can cut your work in half. However, now that I read your comment, I can see how this is confusing. I’ve created an internal GitHub issue to reevaluate this section when we publish version 2.0. For now just refer to Chapter 12.

Thanks a lot for leaving a comment. That helps to improve the book for everyone. Please leave more comments as you work through the book.