Complexity of recursive function

Question

I am reading a problem that I've encountered here with its corresponding solution. The statement is the following:

Given coordinates of a source point (x1, y1) determine if it is possible to reach the destination point (x2, y2). From any point (x, y) there only two types of valid movements: (x, x + y) and (x + y, y). Return a boolean true if it is possible else return false.

I understand how the recursion works for this problem but I was thinking how it works in terms of the complexity. I am thinking about the worst case which is starting from (1,1) to arrive to an arbitrary (x,y) - how many recursive calls are there in this case ? I am having difficulty trying to calculate the number of recursive calls so I would really appreciate an explanation or illustration on the number of calls that there would be. Thanks in advance

Complexity is defined for the algorithm. Can you please provide the algorithm that you use to solve this problem. — Yuri Ginsburg
– Yuri Ginsburg, Commented Aug 27, 2019 at 7:47
stackoverflow.com/a/56598475 describes an O(n) algorithm and hints at an O(log(n)) one. But as Yuri says, the big-O notation is about algorithms and not problems. — Scott Sauyet
– Scott Sauyet, Commented Aug 27, 2019 at 19:42

Hadi GhahremanNezhad · Accepted Answer · 2019-08-27 14:22:17Z

To write a recursive algorithm for this, we can assume something like this:

bool possible(Point src(x1,y1), Point dst(x2,y2))
{
    if((x1 > x2) || (y1>y2))
        return False;
    if(src == dst)
        return True;

    Point p1 = Point(x1 , x1+y1);
    Point p2 = Point(x1+y1 , y1);

    return(possible(p1,dst) || possible(p2,dst));
}

For time complexity we need to consider the maximum number of times that the function is called. If we consider the tree, this would be a Depth First Search and each time we increase the y value until it gets to the point where y > y2. Then we go back to increasing the x value. My guess would be O(max((y2-y1) , (x2-x1)); because in the worst case we go down the tree one by one until the value of x or y (depending on the order in here: return(possible(p1,dst) || possible(p2,dst))) gets larger than the corresponding value of the dst point.

jwezorek · Accepted Answer · 2019-08-27 16:28:14Z

1

Without loss of generality regarding its time complexity, let x1 = y1 = 1 and x2 = y2 = n.

The recursive calls will make a binary tree. Because x1 and y1 are both 1, the highest x and y value at the ith level of the binary tree will be the ith Fibonacci number. Since the ith Fibonacci number is approximately 1.618 to the ith power, the height of the tree is O(log(n)). The number of nodes in a binary tree is O(2^h) where h is the height of the tree, so this algorithm will make O(2^log(n)) recursive calls, which means it is O(n).

answered Aug 27, 2019 at 16:28

jwezorek

10k2 gold badges37 silver badges64 bronze badges

Collectives™ on Stack Overflow

Complexity of recursive function

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related