recurssion

Question

Let T(n) be a function which takes an integer n having k digits as input. The function T(n) finds the maximum number of perfect squares possible by removing either least significant digit or the most significant digit.

For example, consider the number 32492, T(32492) = 3 via sequence
32492→3249→324→24→4
You are given a function IS_SQUARE(a) which tells you whether the integer a is a perfect square or not.
If the time complexity for IS_SQUARE(a) is O(1), what is the time complexity to compute T(n)?

Comments

I think O(2^k) ?

---

Whats the Recurrence Relation ?

---

T(n) = T(n-1) + T(n-1) + O(1)

first T(n-1) for removing digit from left and the other one to remove digit from right and O(1) to check whether it is a perfect square