1
$\begingroup$

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"

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – compque Jun 30 '18 at 2:38
  • $\begingroup$ @compque Ahh, I see! I'll update the answer $\endgroup$ – Draconis Jun 30 '18 at 2:39
  • $\begingroup$ @compque How's that? $\endgroup$ – Draconis Jun 30 '18 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.