Simplifying the Big-O Complexities of this Exponential Algorithm

Question

I have a counting algorithm for which I am trying to get a general description of a large number. It is terribly nesting and terribly exponential. There he is:

1. For each T_i in T 2. For k = 1 to max_k 3. For each of 2^k*(n choose k) items 4. For each t in T_i 5. check if the item is in t...etc. 

Below is a linear idea of ​​each runtime

• This is a simple split, and I'm going to just give it the constant c1.
• max_k is a small number, always less than n, possibly around 4 or 5. I will use k below.
• This loop always executes 2 ^ k * (n selects k) times
• Considering a level 1 constant, we can generalize this line and know that in the worst case it will not be more than 2 ^ n times in the general case, but in the general case it will work from 2 ^ n times, so we will call it (2 ^ n) / s2
• This is a simple if-statement operation inside all of these loops, therefore c3.

Multiplication of all these elements gives:

 c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

Since I want a big-O representation, ignoring constants gives:

 k * 2^k * (n choose k) * (2^n) 

It is known that (n selects k) is bounded above (n * e / k) ^ k, therefore:

 O(k * 2^k * (n * e / k)^k * (2^n)) 

My question is, what can I ignore here ... 2 ^ n is certainly the dominant term, since n is always greater than k and, as a rule, much more. Can this be simplified to O (2 ^ n)? Or O (2 ^ terrible)? Or leave in 2 ^ k, as in O (2 ^ k * 2 ^ n)? (or leave all terms in?)

I understand that if k or max_k can compete or exceed n, then they are vital. But since they always dominate, can they be discarded as members of the lower order polynomial time? I assume that all exponential time disturbances confuse me. Any advice is appreciated.

Answer 1

I understand that if k or max_k can compete or exceed n, then they are vital

True, but vice versa - this does not mean - it cannot be ignored when it comes to a large record O, even if it does not compete with n. It can be ignored only if max_k is bounded by a constant (there exists a constant c such that k <= c ). For example, the O(n * logk) algorithms are not O(n) , since the factor k is unbounded and, therefore, there exists k such that nlogk > c*n for each constant c .

Since the expression you received is a product, all you can ignore is the constants, which in your case are just e getting you O(k*2^k * (n/k)^k * 2^n)

If k bounded, you can remove it from the expression, as well as in the large O notation, and you will get O(n^k* 2^n) . Please note that even in this case, although n^k << 2^n , it still cannot be ignored, because for any constant c there exists some n such that c*2^n < n^k *2^n therefore the algorithm is not O(2^n) .

Smaller factors can be ignored when it comes to adding. If k < n , then O(n + k) = O(n) , since there exist constants c,N such that for all n > N : c*n < n + k , but this, of course, is not true when working with the product.