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

@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.

See this page for additional information on large O symbols.

Related questions