Home > OS >  O(sumof(n)) time complexity
O(sumof(n)) time complexity

Time:10-03

Question is simple and straightforward: is there such thing as a time complexity of O(sumof(n))

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

  • Related