# Exponential Time Classification

If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time?

print([2,4,8,16]) #operations:1
print([1,4,8,16]) #operations:2
print([1,3,8,16]) #operations:3
print([1,2,8,16]) #operations:4
print([1,1,8,16])  #operations:5
print([1,1,7,16])  #operations:6
print([1,1,6,16])  #operations:7
print([1,1,..,16]) #operations+=1
print([..])       #operations+=1
print([1,1,1,1])  #operations: 2**(n+1)-2 :: O(2**n)?


Does one add the number of operations or the complexity of each operation?

Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

If the complexity is constant time would I need each operation to be O(2**n) for the algorithm to be classified as exponential time? O(2**n)*(2**(n+1)-2) reducing to O(2**n) or would it reduce to double exponential time: O(2**(2**n))?

Here is some python code for such a naive algorithm:

orig_lst=[2,4,8,16]
out_lst=orig_lst[:]
ops=0
n=len(out_lst)
for ind,el in enumerate(out_lst):
for dec in range(el,0,-1):
ops+=1
out_lst[ind]=dec
print(orig_lst,"->",out_lst,"number of operations:",2**(n+1)-2,"==",ops)


Which prints: "[2, 4, 8, 16] -> [1, 1, 1, 1] number of operations: 30 == 30"

Does one add the number of operations or the complexity of each operation?

This is a good question! And the answer is, "it depends".

In any model of computation, some type of operation is considered "fundamental", and this operation is considered to run in $O(1)$. For example, some models consider multiplication to be fundamental. But others consider multiplication exponential in the number of bits.

No matter what, though, your algorithm is going to be doing $2^n$ decrement operations on the last element of the list, so it's always going to be $\Omega(2^n)$ (where the omega means "at least", as opposed to omicron's "at most").

Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

I'm not sure I understand this part of the question. $O(1) \times (2^{n+1}-2)$ is $O(2^n)$, not $O(1)$.

However, your time complexity certainly isn't double-exponential. As you noted, you're doing $2^{n+1}-2$ decrement operations, so if you consider decrement to be constant, the total time is $O(2^{n+1}-2) = O(2^n)$.

Even if you did an additional $O(2^n)$ operation for each decrement, the time complexity would only be $O(2^n) \times O(2^n) = O(2^{2n})$.

• Thanks for the clarification. The second part of the question hinged on the answer to the first. The double exponential time question was about a different hypothetical algo that in addition to the decrement the algo also performed a O(2**n) operation during each decrement. – compque Jun 30 '18 at 2:38
• @compque Ahh, I see! I'll update the answer – Draconis Jun 30 '18 at 2:39
• @compque How's that? – Draconis Jun 30 '18 at 2:41