educative.io

Correct time complexity of recursive solution should be O(x^n) where x is largest element in array and n is total number of elements

Courses
,
#1

A node in recursion tree can split into x children if the node has value x. Assuming x is largest value, we can assume that each element in array has x value.
So each node in recursion tree has x children and depth of tree is n.
Hence O(x^n)

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5685057352105984
emphasized text

#2

Hello @Mandar_Pande

Thank you for reaching out. Let’s look at the time complexity step by step. From every index 0 to n-1, there are two possibilities: either take a jump or do not take a jump. And since there are n number of elements inside the array and every element has 2 possibilities (jump or not jump), the complexity to reach the end of array will be O(2^n). Finding the jumps is an exponential function of n since we are exploring all the possibilities.

Hope this helps!

1 Like