4 ms·

Show HN: Boat – Big O analysis tool

24 points by logv 8y ago

logv 8y ago
BOAT is a quick tool I made for analyzing and comparing the Big O growth rate of mathematical functions. I built it to help students get a sense of Big O notation, as its a common class exercise to have to rank several math functions in terms of their Big O. BOAT works by trying to find an upper and lower bound of a given math function by comparing the function against a set of known functions. If it can't find a tight bound, it tries to find an upper bound. If it's given two functions, it will try to locate their crossover point (if any) using a binary search, as well as compare their growth rates to determine which will eventually grow faster. It might get some wrong (I'm curious which) as it only has a handful of function classes. The last feature it has is an automated master/muster theorem solver. It's pretty simple - you give it the values of a recurrence relation and it tells you the big O. Thanks for looking!
nathell 8y ago
Doesn't appear to be very accurate. https://boat.algorithm.city/analyzer/?&f=N*lg(N)*lg(lg(N) https://boat.algorithm.city/analyzer/?&f=N*lg(N)*lg(lg(N)) "The Big Theta of N * lg(N) * lg(lg(N)) is O(n * lg(n))"
- logv 8y ago
  Thanks for the feedback and good catch! The list of big O classes is the following: var classes = [ define_func("0"), define_func("1"), define_func("lg(n)"), define_func("sqrt(n)"), define_func("n"), define_func("n * lg(lg((n)))"), define_func("n * lg(n)"), define_func("n * sqrt(n)"), define_func("n**2"), define_func("n**3"), define_func("n**4"), define_func("2**n"), define_func("n**n"), define_func("factorial(n)"), define_func("2**(2**n)"), define_func("n**(n**n)"), ]; lg(lg(N)) is very small, for 1e30, the value is approximately ~6 and at 1e60 it is ~7.6, at which point lg(lg(N)) is pretty much a constant value (or trivial), but yes - it is technically included in the growth rate, but for practical purposes can probably be ignored
gitgud 8y ago
Great name! So it analyses math equations you input? I would call this a simulation, as my first impression was that it would analyse source code...
- logv 8y ago
  Yes, it analyzes a formula or recurrence relation - sorry to get your hopes up :-D I wish it could analyze source code, but the halting problem says that would be a bit difficult. I think one could execute source code with varying size inputs to get an idea of a function's growth (assuming the function does halt), but I haven't thought about what that entails PS: maybe I should have named it BOFAT (Big O Formula Analyzer Tool)
  - mhh__ 8y ago
    Surely the halting problem only applies in the general case, i.e. given a ideal enough language you could use heuristics or give results applicable only when in xyz conditions e.g. when these nested for loops are in action it's O(n^2)
    - deleted 8y ago
      [deleted]
    - logv 8y ago
      Yes, this is likely true - I really need to think about it more, though. I don't know how to do static or runtime analysis, so I can't say much about it
arthev 8y ago
The Big Theta of N^N^N^N is O(n * sqrt(n)) :)
- logv 8y ago
  wow, that's way off! for n = 2, n^n^n^n returns 65536. for n = 3, javascript thinks its infinity. i guess BOAT should start using decimal values for n so we can detect this problem.

24 points by logv 8y ago

logv 8y ago

BOAT is a quick tool I made for analyzing and comparing the Big O growth rate of mathematical functions. I built it to help students get a sense of Big O notation, as its a common class exercise to have to rank several math functions in terms of their Big O. BOAT works by trying to find an upper and lower bound of a given math function by comparing the function against a set of known functions. If it can't find a tight bound, it tries to find an upper bound. If it's given two functions, it will try to locate their crossover point (if any) using a binary search, as well as compare their growth rates to determine which will eventually grow faster. It might get some wrong (I'm curious which) as it only has a handful of function classes. The last feature it has is an automated master/muster theorem solver. It's pretty simple - you give it the values of a recurrence relation and it tells you the big O. Thanks for looking!

nathell 8y ago

Doesn't appear to be very accurate. https://boat.algorithm.city/analyzer/?&f=N*lg(N)*lg(lg(N) https://boat.algorithm.city/analyzer/?&f=N*lg(N)*lg(lg(N)) "The Big Theta of N * lg(N) * lg(lg(N)) is O(n * lg(n))"

logv 8y ago
Thanks for the feedback and good catch! The list of big O classes is the following: var classes = [ define_func("0"), define_func("1"), define_func("lg(n)"), define_func("sqrt(n)"), define_func("n"), define_func("n * lg(lg((n)))"), define_func("n * lg(n)"), define_func("n * sqrt(n)"), define_func("n**2"), define_func("n**3"), define_func("n**4"), define_func("2**n"), define_func("n**n"), define_func("factorial(n)"), define_func("2**(2**n)"), define_func("n**(n**n)"), ]; lg(lg(N)) is very small, for 1e30, the value is approximately ~6 and at 1e60 it is ~7.6, at which point lg(lg(N)) is pretty much a constant value (or trivial), but yes - it is technically included in the growth rate, but for practical purposes can probably be ignored

gitgud 8y ago

Great name! So it analyses math equations you input? I would call this a simulation, as my first impression was that it would analyse source code...

logv 8y ago
Yes, it analyzes a formula or recurrence relation - sorry to get your hopes up :-D I wish it could analyze source code, but the halting problem says that would be a bit difficult. I think one could execute source code with varying size inputs to get an idea of a function's growth (assuming the function does halt), but I haven't thought about what that entails PS: maybe I should have named it BOFAT (Big O Formula Analyzer Tool)
- mhh__ 8y ago
  Surely the halting problem only applies in the general case, i.e. given a ideal enough language you could use heuristics or give results applicable only when in xyz conditions e.g. when these nested for loops are in action it's O(n^2)
  - deleted 8y ago
    [deleted]
  - logv 8y ago
    Yes, this is likely true - I really need to think about it more, though. I don't know how to do static or runtime analysis, so I can't say much about it

arthev 8y ago

The Big Theta of N^N^N^N is O(n * sqrt(n)) :)

logv 8y ago
wow, that's way off! for n = 2, n^n^n^n returns 65536. for n = 3, javascript thinks its infinity. i guess BOAT should start using decimal values for n so we can detect this problem.