Cycle and cord

Implementation

Time and Space Complexity

Time Complexity: Since essentially the ‘dp’ array is being traversed x times, the average and the worst-case time complexity comes out to be O(N²)

Space Complexity: We are using auxiliary space to carry out dynamic programming. We are using a ‘dp’ array equal to the size of the number of points in the circle. Hence the space complexity is O(N)

FAQs

1). What is the recurrence relation of the above-mentioned problem?

 Ans: Here, ways(n) = sum( i=0 to n-1) {ways(n) * ways(n-i-1)}

If we assume there are i points in a set, then automatically there would N-i-1 points in other since we already used a pair of points for segregation. 

2). What are the time and space complexity of the algorithm implemented above?

Ans: The average time complexity, as we devised earlier, was O(N²). The auxiliary space required was of the order O(N). 

3). Why the dynamic programming approach? 

Ans: Using memoization greatly improves the time complexity of such problems. From a point where problems like these are almost infeasible via the brute force methods. 

Key Takeaways

‘The Circle and chord’ is one of the peculiar dynamic programming problems. Implementing and understanding this would make you better prepared to handle more interesting problems based on the concept of dynamic programming. 

Check out this problem - Count Ways To Reach The Nth Stair 

Devising a recurrence relation is the key to tackling such problems. Problems like these are quite favourite among the recruiters. Check out our curated interview preparation courses put together by expert faculty of industry experts to crack your next product-based company interview.