4 ms·

Is it really O(2^N)? If so, how'd you determine that so quickly? I'd like that intuition. I do ok at big-O reasoning, but in this case turning probabilities in

Is it really O(2^N)? If so, how'd you determine that so quickly? I'd like that intuition. I do ok at big-O reasoning, but in this case turning probabilities into big-O eludes me. In the video, there's an opposite maze which biases the guests to walk towards the exit, making it much easier to solve. What's the big-O of that version?

jchw 6y ago
I think the key insights are: - only the most significant (in terms of exponentially) factor(s) matters for big O (i.e. if you have a linear factor, the constant time factor is ignored) - You have to determine whether you are talking worst case or average case or best case. Assuming average case I’d guess the opposite maze is O(n) because the time expands linearly with number of segments. (Disclaimer: I am not formally educated in computer science, so admittedly I am not up to snuff on the mathematical side of things. Hopefully I am close enough here.) edit: Oops, I failed to actually cover any time complexity calculation at all. I do not know if my approach is correct, but here's how I view the original: def walk_path(n): // probability of _not_ recursing is (1/n^2) // probability of _recursing_ is (1 - 1/n^2) // likelihood of recursing doubles with n // therefore, the average case of this loop is O(2^n) for (i : 0 -> n) if (random() < 0.5) walk(); // = O(1) else // Ignoring the actual walking on the branch, we just pretend we turn around directly. for (j : i -> 0) // = O(n/2) walk(); return walk_path(n); and the opposite is straight forward, since the branches are 'constant time' - so it's more like a straight loop.
- nwallin 6y ago
  In this instance, you're only concerned with the average case. Worst case is infinite: you just always take the path back in the direction of the entrance, and never even get past the first inlet. Best case is O(n): you always take the path forward.
  - jchw 6y ago
    Yep, sorry, it quickly became apparent after rereading this that the original analysis was not worst-case. I have revised my comment to also include how I view calculating the actual time complexity since I didn't actually do that initially.
deleted 6y ago
[deleted]
nitrogen 6y ago
I'm not 100% confident in my explanation below, but maybe it's something like this, if we don't have prior knowledge of the asymptotic behavior of random walks: The measured values are empirically exponential with a factor of 1.424 per indentation. If we assume that as an upper bound (which I don't think is quite right), then we have O(1.424^N) where N is the number of indentations. Any exponent can be written in terms of any other base by multiplying by a constant. Since we often use base 2, we can choose to rewrite it in base 2 as O(2^(K*N)), where K is approximately 0.51. Constant terms can be ignored in big O notation, so we can just drop the K to get O(2^N) (I am less sure about dropping a constant within the exponent).
- karatinversion 6y ago
  You cannot drop constant terms from exponents in big-O notation.
- gopiandcode 6y ago
  You can't drop constant multiplicative terms in an exponent - O(2^n) is not equivalent to O(2^(2n)) as O(4^n) \= O(2^n) (the first one grows a lot faster).
im3w1l 6y ago
Let's pose the problem mathematically. Initial state is (0, forwards). State (0, *) transitions to (1, forwards) For k > 1, state (k, forwards) transitions to (k+1, forwards) with 5/8 probability and to (k-1, backwards) with probability 3/8. For k > 1, state (k, backwards) transitions to (k+1, forwards) with 1/8 probability and to (k-1, backwards) with probability 7/8. My intuition is that this very much resembles a biased walk so it should take exponential time. But there is the "momentum" to take into account. Edit: It looks like we can use https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expected_number_of_steps https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...
- gbrown 6y ago
  Came here for this - I knew there must be an analytical solution involving Markov chains.
  - tetha 6y ago
    I'm pretty sure this can be modeled with markov chains. Your vertices would be (x, y, f), f being facing. Edges are along the lines of (x, y, 0) - (x+1, y, {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y, 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1, {0,1,2,3}\2). Probabilities are modeled in the video and need to be rotated 4 times for the four facings. After that, I just don't recall my eigenvector calculation anymore. It feels like a good markov exercise, though.
contravariant 6y ago
Note that they likely messed up slightly, it'll be more or less exponential in some base but possibly not 2. However big O notation does require you to get the base correct (or at least provide an upper bound), you can't ignore it like you can ignore a multiplicative or additive constant.
ascar 6y ago
I'm also absolutely not an expert on this (M.Sc. CS). I would argue using Big O here is wrong and Landau symbols are not well defined on Markov chains/probabilistic turing machines. The point of Landau symbols is to give asymptotic bounds of functions with N approaching a certain value (usually positive infinity). My intuition says that the runtime of a probabilistic turing machine isn't necessarily a function tho (i.e. a deterministic association between any N and time(N)). Google wasn't really helpful on complexity theory of Markov chains and based on the research papers that pop up it seems far enough away that I would avoid using Big O in this scenario. Probabilistic turing machines even seem to have their own complexity classes (https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine).
- red0point 6y ago
  Sure you can use Big O, just look at it as the expected runtime. For example, QuickSort is O(n^2) in worst case, but expected O(nlog(n)).
  - leapis 6y ago
    For probabilistic algorithms, we can look at the worst-case-w.h.p runtime: that is, a randomized quicksort, although technically still having an "absolute" worst case of O(n^2), actually is considered to have a worst case of O(nlog(n)), with probability 1 - 1 / (n^c) when bounded by Chernoff, as shown here: https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lectures/Lec13-Ineq.pdf https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...

jchw 6y ago

I think the key insights are: - only the most significant (in terms of exponentially) factor(s) matters for big O (i.e. if you have a linear factor, the constant time factor is ignored) - You have to determine whether you are talking worst case or average case or best case. Assuming average case I’d guess the opposite maze is O(n) because the time expands linearly with number of segments. (Disclaimer: I am not formally educated in computer science, so admittedly I am not up to snuff on the mathematical side of things. Hopefully I am close enough here.) edit: Oops, I failed to actually cover any time complexity calculation at all. I do not know if my approach is correct, but here's how I view the original: def walk_path(n): // probability of _not_ recursing is (1/n^2) // probability of _recursing_ is (1 - 1/n^2) // likelihood of recursing doubles with n // therefore, the average case of this loop is O(2^n) for (i : 0 -> n) if (random() < 0.5) walk(); // = O(1) else // Ignoring the actual walking on the branch, we just pretend we turn around directly. for (j : i -> 0) // = O(n/2) walk(); return walk_path(n); and the opposite is straight forward, since the branches are 'constant time' - so it's more like a straight loop.

nwallin 6y ago
In this instance, you're only concerned with the average case. Worst case is infinite: you just always take the path back in the direction of the entrance, and never even get past the first inlet. Best case is O(n): you always take the path forward.
- jchw 6y ago
  Yep, sorry, it quickly became apparent after rereading this that the original analysis was not worst-case. I have revised my comment to also include how I view calculating the actual time complexity since I didn't actually do that initially.

deleted 6y ago

[deleted]

nitrogen 6y ago

I'm not 100% confident in my explanation below, but maybe it's something like this, if we don't have prior knowledge of the asymptotic behavior of random walks: The measured values are empirically exponential with a factor of 1.424 per indentation. If we assume that as an upper bound (which I don't think is quite right), then we have O(1.424^N) where N is the number of indentations. Any exponent can be written in terms of any other base by multiplying by a constant. Since we often use base 2, we can choose to rewrite it in base 2 as O(2^(K*N)), where K is approximately 0.51. Constant terms can be ignored in big O notation, so we can just drop the K to get O(2^N) (I am less sure about dropping a constant within the exponent).

karatinversion 6y ago
You cannot drop constant terms from exponents in big-O notation.
gopiandcode 6y ago
You can't drop constant multiplicative terms in an exponent - O(2^n) is not equivalent to O(2^(2n)) as O(4^n) \= O(2^n) (the first one grows a lot faster).

im3w1l 6y ago

Let's pose the problem mathematically. Initial state is (0, forwards). State (0, *) transitions to (1, forwards) For k > 1, state (k, forwards) transitions to (k+1, forwards) with 5/8 probability and to (k-1, backwards) with probability 3/8. For k > 1, state (k, backwards) transitions to (k+1, forwards) with 1/8 probability and to (k-1, backwards) with probability 7/8. My intuition is that this very much resembles a biased walk so it should take exponential time. But there is the "momentum" to take into account. Edit: It looks like we can use https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expected_number_of_steps https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...

gbrown 6y ago
Came here for this - I knew there must be an analytical solution involving Markov chains.
- tetha 6y ago
  I'm pretty sure this can be modeled with markov chains. Your vertices would be (x, y, f), f being facing. Edges are along the lines of (x, y, 0) - (x+1, y, {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y, 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1, {0,1,2,3}\2). Probabilities are modeled in the video and need to be rotated 4 times for the four facings. After that, I just don't recall my eigenvector calculation anymore. It feels like a good markov exercise, though.

contravariant 6y ago

Note that they likely messed up slightly, it'll be more or less exponential in some base but possibly not 2. However big O notation does require you to get the base correct (or at least provide an upper bound), you can't ignore it like you can ignore a multiplicative or additive constant.

ascar 6y ago

I'm also absolutely not an expert on this (M.Sc. CS). I would argue using Big O here is wrong and Landau symbols are not well defined on Markov chains/probabilistic turing machines. The point of Landau symbols is to give asymptotic bounds of functions with N approaching a certain value (usually positive infinity). My intuition says that the runtime of a probabilistic turing machine isn't necessarily a function tho (i.e. a deterministic association between any N and time(N)). Google wasn't really helpful on complexity theory of Markov chains and based on the research papers that pop up it seems far enough away that I would avoid using Big O in this scenario. Probabilistic turing machines even seem to have their own complexity classes (https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine).

red0point 6y ago
Sure you can use Big O, just look at it as the expected runtime. For example, QuickSort is O(n^2) in worst case, but expected O(nlog(n)).
- leapis 6y ago
  For probabilistic algorithms, we can look at the worst-case-w.h.p runtime: that is, a randomized quicksort, although technically still having an "absolute" worst case of O(n^2), actually is considered to have a worst case of O(nlog(n)), with probability 1 - 1 / (n^c) when bounded by Chernoff, as shown here: https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lectures/Lec13-Ineq.pdf https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...