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
Answers: 1

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

1
2022-06-07 15:08:46
Source