- 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);