3 ms·

Agreed. It's such a strange statement I suspect he meant something else but I can't see what.

adrianmonk 7y ago
I guess, informally, people sometimes say exponential when they just mean "way too much" or "extreme". Someone might say, for example, "The party was already getting out of hand, but then my roommate's drinking buddies showed up and that's when things got exponentially worse."
akamoonknight 7y ago
Could they have meant exponentially with respect to using binary search? That is, using linear search is exponentially worse than using binary search on a sorted data set.
- adrianmonk 7y ago
  That's an interesting theory. It is indeed exponentially worse then. Binary search is O(log N), and linear search is O(N). If you let M=log N, then binary search is O(M) and linear search is O(e^(log N)) = O(e^M). So viewed that way, it's O(M) vs. O(e^M), an exponential relationship. But the blog would still not be 100% right because it adds a qualifier. It says "grows exponentiality with the size of the dataset".
  - Liquid_Fire 7y ago
    Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
    - tempguy9999 7y ago
      Nitpick upon nitpick, the base may be 2 rather than e but IIRC the difference between lg(n) and log2(n) is a constant, and the log/lg term dominates, so it still is 0(log). I think. Big fleas have little fleas upon their backs to bite 'em \ And little fleas have lesser fleas, and so, ad infinitum. (https://en.wikipedia.org/wiki/The_Siphonaptera> https://en.wikipedia.org/wiki/The_Siphonaptera>
      - thethirdone 7y ago
        Nitpick on Nitpick on Nitpick, it is indeed O(2^m) and not O(e^m). Those are not the same complexity. Logs get to not care, but when we exponentiate it matters.
  - claes-magnus 7y ago
    I want to try attempt explaining what I meant. @adriamonk: if you have the time, feel free to help me out here. :) First, my point relates to JavaScript. ``` Take this code: const list = [2,1,2,"4", 5]; console.log( list.sort((a,b) => a-b) ); // [1, 2, 2, "4", 5] ``` This is kind of correct (or wrong), depending on how to view things. But I think we must acknowledge this as a part of the language design of JavaScript. However, using strict eq... ``` console.log( list.findIndex((value) => value === 4) ); // -1 ``` Correct, sure. On the other hand... ``` console.log( list.findIndex((value) => value == 4) ); // 3 ``` But now we're using a non strict form of equality. In JavaScript, the aspects of the language described above can cause a problem concerning binary search. Because of JSs lack of strictness, we can't trust our data in the same way as in C or Rust or other languages (even though TypeScript could save us). Sure if the preconditions aren't met, then we can't use BS. My point is that even though another language still would have to sort the elements in an array, we would know that all elements were of the same type in an array. As programmers we want the behavior of our code to be predictable. And my point - I don't know if it is valid though - is that in JavaScript we can't. Therefore we would have to check every value in the array beforehand, and in JS we would have to do this linearly. I don't know if I misuse the terminology now, in that case, please tell me so (and I will be at least a bit wiser). My main point is that the big O of binary search is irrelevant in the context of JavaScript, if we're not 100% sure that our array is sorted and of the same type. Many other languages would have the first problem (we must trust the array to sorted), while JavaScript has to problems and this is more unpredictable. And I think we can only ensure this by the use of a linear method in JS.

I guess, informally, people sometimes say exponential when they just mean "way too much" or "extreme". Someone might say, for example, "The party was already getting out of hand, but then my roommate's drinking buddies showed up and that's when things got exponentially worse."

akamoonknight 7y ago

Could they have meant exponentially with respect to using binary search? That is, using linear search is exponentially worse than using binary search on a sorted data set.

adrianmonk 7y ago
That's an interesting theory. It is indeed exponentially worse then. Binary search is O(log N), and linear search is O(N). If you let M=log N, then binary search is O(M) and linear search is O(e^(log N)) = O(e^M). So viewed that way, it's O(M) vs. O(e^M), an exponential relationship. But the blog would still not be 100% right because it adds a qualifier. It says "grows exponentiality with the size of the dataset".
- Liquid_Fire 7y ago
  Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
  - tempguy9999 7y ago
    Nitpick upon nitpick, the base may be 2 rather than e but IIRC the difference between lg(n) and log2(n) is a constant, and the log/lg term dominates, so it still is 0(log). I think. Big fleas have little fleas upon their backs to bite 'em \ And little fleas have lesser fleas, and so, ad infinitum. (https://en.wikipedia.org/wiki/The_Siphonaptera> https://en.wikipedia.org/wiki/The_Siphonaptera>
    - thethirdone 7y ago
      Nitpick on Nitpick on Nitpick, it is indeed O(2^m) and not O(e^m). Those are not the same complexity. Logs get to not care, but when we exponentiate it matters.
- claes-magnus 7y ago
  I want to try attempt explaining what I meant. @adriamonk: if you have the time, feel free to help me out here. :) First, my point relates to JavaScript. ``` Take this code: const list = [2,1,2,"4", 5]; console.log( list.sort((a,b) => a-b) ); // [1, 2, 2, "4", 5] ``` This is kind of correct (or wrong), depending on how to view things. But I think we must acknowledge this as a part of the language design of JavaScript. However, using strict eq... ``` console.log( list.findIndex((value) => value === 4) ); // -1 ``` Correct, sure. On the other hand... ``` console.log( list.findIndex((value) => value == 4) ); // 3 ``` But now we're using a non strict form of equality. In JavaScript, the aspects of the language described above can cause a problem concerning binary search. Because of JSs lack of strictness, we can't trust our data in the same way as in C or Rust or other languages (even though TypeScript could save us). Sure if the preconditions aren't met, then we can't use BS. My point is that even though another language still would have to sort the elements in an array, we would know that all elements were of the same type in an array. As programmers we want the behavior of our code to be predictable. And my point - I don't know if it is valid though - is that in JavaScript we can't. Therefore we would have to check every value in the array beforehand, and in JS we would have to do this linearly. I don't know if I misuse the terminology now, in that case, please tell me so (and I will be at least a bit wiser). My main point is that the big O of binary search is irrelevant in the context of JavaScript, if we're not 100% sure that our array is sorted and of the same type. Many other languages would have the first problem (we must trust the array to sorted), while JavaScript has to problems and this is more unpredictable. And I think we can only ensure this by the use of a linear method in JS.