It's got to be O(n) for a large list of integers.

Edited: corrections made based on comments regarding O(n) performance of [::].

TL;DR: It could be O(n), but your version is O(n²).

Remember that all of the big-O notations assume "times a constant". That is, O(n) really means O(k * n), and O(log n) really means O(k * log n).

Let's look at your first example:

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

The first line is assert plus compare plus len. The len operation is a constant time for lists and tuples (But it might not be with some other data structure! Beware!), compare is a constant time, and the assert is effectively a constant time, because if it ever fails the whole thing blows up and we stop computing. So let's just call assert a function call plus a comparison plus a return.

Now, how many times does this function get called? Well, the termination condition obviously represents one time, and every other time it's recursing on a list that is one shorter than the previous list. So the function will be called len(numberSequence) times, which is n for our purposes.

So we have

  1 * call (for the user calling us)
+ n * assert 
+ n * len 
+ n * compare

Next, we have the if statement that marks the termination condition for your recursion. Obviously, this statement will only be successful once (it's the termination condition, right? Only happens at the end...) so that's a comparison each time, and once per sum it's a return of a constant index.

  n * compare
+ 1 * constant index
+ 1 * return

Finally, there is the else: branch. I'm pretty sure you have a bug, and it should really be this (note position of colon):

        return sum(numberSequence[:-1]) + numberSequence[-1]

In that case you return the sum of a constant negative index lookup and a recursive function call of a slice. You only do this when it's NOT the end of the recursion, so n-1 times.

  (n - 1) * constant negative index lookup
+ (n - 1) * slice
+ (n - 1) * recursive call
+ (n - 1) * return

But wait! If you look around for people asking about how to make a copy of a list, you'll find that one common Python idiom is copy = orig[:]. The reason for this is that a slice operation makes a copy of the subrange of the list it is slicing. So when you say numberSequence[:-1] what you're really saying is copy = [orig[i] for i in range(0, len(orig)-1)].

This means that the slice operation is O(n), but on the plus side it's written in C. So the constant is a much smaller one.

Let's add those up:

  1 * call
+ n * assert 
+ n * len
+ n * compare
+ n * compare
+ 1 * constant index 
+ 1 * return
+ (n - 1) * constant negative index lookup
+ (n - 1) * (c * n) slice
+ (n - 1) * recursive call
+ (n - 1) * return

If we assume that constant index and constant negative index take the same time, we can merge them. We can obviously merge the returns and the calls. Which leaves us with:

   n * call
 + n * assert 
 + n * len
 + n * compare
 + n * compare
 + n * constant (maybe negative) index 
 + n * return
 + (n - 1) * (c * n) slice

Now according to "the rules," this is O(n²). Which means that all the details of O(n) behavior fall by the wayside in favor of that big, fat O(n²).

However:

If the len operation were not O(1) - that is, constant time - then the function might well become O(n²) because of that.

If the index operations were not O(1), because of underlying implementation details, the function might become O(n²) or O(n log n) because of that.

So you have implemented an algorithm that could be O(n) using a Python operator that is inherently O(n) itself. Your implementation is "inherently" O(n²). But it can be fixed. Even if fixed, things outside of your control could make your code slower. (But, that's outside your control, so ... ignore it!)

How can we fix your code to make it O(n)? By getting rid of the slice! You don't need that anyway, right? You just need to track the range.

def sum(numberSequence, start=0, end=None):
    assert (len(numberSequence) > 0)
    if end is None:
        end = len(numberSequence) - 1
    if end == start:
        return numberSequence[start]
    else:
        return sum(numberSequence, start, end-1) + numberSequence[end]

In this code, I'm doing pretty much the same thing that you did, with two differences. First, I've added a special case to handle being called by an end user with only the sequence as an argument. And second, of course, there is no slice. With that out of the way, the code is no longer inherently O(n²).

You can do the same math, and make the same changes, to your other example, but it's more complex. However, I will remind you that the sum of 2ⁱ for i = 0..n-1 is 2ⁿ - 1. As @lollercoaster points out, there ain't no such thing as a free lunch: you have to add up all the numbers.

To expand on the answer "obviously not", consider the array $i_1, i_2, \dots, i_N$ which is sorted. Then suppose we had a way to compute the sum in logarithmic time. Since we can only visit at most $\log(N)$ of the elements, we did not visit at least one element $i_k$. Now set $i_k := \frac{i_k + i_{k+1}}{2}$ (or $\frac{i_{k-1}+i_k}{2}$ if $k = N$) to change the sum in a way that our algorithm could not detect.

(… and as David now notes, you left crucial assumptions out of the question. Please don't do that.)