# Computational complexity of this algorithm

Consider a function $f(n,k)$ for $n,k\in\mathbb{N}$ and also an algorithm that applies that function. The framework of the algorithm is as adheres to:

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

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

0
2022-06-07 14:40:35
Source Share

@Listing is proper.

The inquiry examinations to see if one identifies that

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


For instance,

|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 keep in mind that if f (n, k) were to be O (n), after that it would certainly additionally be O (2 ^ n) ; nonetheless, in this instance, it is not O (n) given that (as @Listing mentioned) k' can get to values a lot more than n given that k' tackles all values approximately 2 ^ n - 1 (eg, when k = 2 ^ n - 1, k' = 2 ^ n - 1), and also|2 ^ n - 1|>|n|for all constants A as n mosts likely to infinity.