In Bogosort, the lower bound for random version is unbounded which is O(inf). You can even turn the Rubiks Cube problem into a sorting problem of finding path from starting position to solved position, involving a series of moves. I’m not sure if there are more than one set of shortest path solution to each scenario.
Oh, I’m not making the argument that randomly permuting the Rubik’s Cube will always solve it in a finite time, but that it might. I think it has a better chance of solving it than the chicken. The chicken might get lucky and knock the Rubik’s Cube off the edge of a cliff and it might rotate by accident, but other than that, the chicken isn’t going to do much work on solving it in the first place. Meanwhile, randomly permuting might solve it (or might not solve it in the worst case). I just think that random permutations have a higher chance of solving it than the chicken, but I can’t formally prove that.
In Bogosort, the lower bound for random version is unbounded which is O(inf). You can even turn the Rubiks Cube problem into a sorting problem of finding path from starting position to solved position, involving a series of moves. I’m not sure if there are more than one set of shortest path solution to each scenario.
Oh, I’m not making the argument that randomly permuting the Rubik’s Cube will always solve it in a finite time, but that it might. I think it has a better chance of solving it than the chicken. The chicken might get lucky and knock the Rubik’s Cube off the edge of a cliff and it might rotate by accident, but other than that, the chicken isn’t going to do much work on solving it in the first place. Meanwhile, randomly permuting might solve it (or might not solve it in the worst case). I just think that random permutations have a higher chance of solving it than the chicken, but I can’t formally prove that.