Computational complexity of this algorithm

Question

Consider a function $f(n,k)$ for $n,k\in\mathbb{N}$ and an algorithm that implements that function. The structure of the algorithm is as follows:

• do some calculations that take $O(n)$ time
• define $k' = k \mod 2^n$
• do some calculations that take $O(k')$ time

What is the computational complexity of this algorithm? Specifically, is it $O(n)$ or $O(2^n)$?

Answer 1

@Listing is correct.

The question tests to see if one recognizes that

f(n,k)
= *O*(n) + *O*(1) + *O*(k')
= *O*(n) + *O*(1) + *O*(2^n)
= *O*(2^n)

For example,

|f(n,k)|
<= M|n| + C|1| + N|k'| as x goes to infinity, and some constant M and N that satisfy:
    (a) |work in part one| <= M|n|
    (b) |definition of part two| <= C|1| (by assumption)
    (c) |work in part three| <= N|k'|
as given or assumed.

<= M|n| + C|1| + N|2^n| since |k'| <= 1|2^n| as x goes to infinity (all k' are bounded above by 2^n by the definition of mod)

<= N|2^n| since | M|n| + C|1| + N|2^n| | <= 2N|2^n| as x goes to infinity

We note that if f(n,k) were to be O(n), then it would also be O(2^n); however, in this case, it is not O(n) since (as @Listing stated) k' can reach values much greater than n since k' takes on all values up to 2^n-1 (eg, when k=2^n-1, k'=2^n-1), and |2^n-1| > A|n| for all constants A as n goes to infinity.

See this page for more information on big O notation.