CODEWITHSUNDEEP
recursiontime-complexity
user156441
user156441

Reputation: 185

Complexity of recursive function

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

Upvotes: 1

Views: 429

Answers (2)

jwezorek
jwezorek

Reputation: 9525

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

Upvotes: 1

Hadi GhahremanNezhad
Hadi GhahremanNezhad

Reputation: 2445

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.

Upvotes: 1

Related Questions