python - 求和算法的时间复杂度

我看过以前的文章，仍然在努力寻找这两个递归算法的t（n）和big o，每一个都以一个数字序列作为参数，对列表中的所有数字（除了最后一项）求和，然后将求和添加到最后一项。谁能给我点光吗？

def sum(numberSequence):
    assert (len(numberSequence) > 0)
    if (len(numberSequence) == 1):
        return numberSequence[0]
    else:
        return sum(numberSequence[-1]) + numberSequence[:-1]

（我相信bigo是O(n)最坏的情况是，函数被调用n-1次，但不确定当它只是列表的一部分求和时会发生什么。我觉得这似乎不对。

def binarySum(numberSequence):
    assert (len(numberSequence) > 0)
    breakPoint = int(len(numberSequence)/2)
    if (len(numberSequence) == 1):
        return numberSequence[0]
    else:
        return binarySum(numberSequence[:breakPoint]) + binarySum(numberSequence[breakPoint:])

我更迷茫于此，我认为大o是T(n) = n x n-1 + n = O(n)因为它是二进制搜索，但整个列表并没有被分成一半，只有大部分列表。
任何帮助都将不胜感激。

最佳答案

你在把一个任意大小，任意顺序的N数字的列表相加。
你不会找到一个聪明的方法，在没有限制的情况下更快地做到这一点。
它总是Ω(N)的（下限是N加法运算-你不会得到比这更好的结果）。
正如下面的一位评论者所说，你的算法实际上可能更糟——只是不可能更好。