0
$\begingroup$

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)$?

  • 3
    You can choose $k=2^n-1$ so your last step will always take $O(2^n)$ time2011-05-20

1 Answers 1

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.