Question is simple and straightforward: is there such thing as a time complexity of
and is this the proper way to write it? I am asking because this program I wrote:
def check(self, front, s, back):
if(s[front:back] == s[front:back][::-1]):
return s[front:back]
else:
return self.check(front, s, back-1)
def checkIter(self, front, s, back, longest):
r = self.check(front, s, back)
if(len(r) >= len(longest)): longest = r
if(front < back):
return self.checkIter(front 1,s,back, longest)
else:
return longest
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
return self.checkIter(0,s,len(s),"")
on input of longestPalindrome('cbbd')
it runs ~10 times producing the ouputs:
"cbbd" "cbb" "cb" "c" "bbd" "bb" "b" "bd" "b" "d"
. On a simalar input of longestPalindrome('cbbda')
gives:
"cbbda" "cbbd" "cbb" "cb" "c" "bbda" "bbd" "bb" "b" "bda" "bd" "b" "da" "d" "a"
So this can't be O(n)
CodePudding user response:
The specified sum is equal to n(n 1)/2
. Hence, it is in O(n^2)
.