0
$\begingroup$

I have the following algorithm

x = 0
S = {}
k = 1
while x + a[k] < n do
    S = S + {k}
    x = x + a[k]
    k = k + 1
end

where a[k] is a positive integer.

What is the time complexity in terms of number of iterations of this algorithm?

I tried to compute the number of operations. As I understand, I should find how many steps are required in order for $x$ to be equal to $n$ by adding $a_k$ in each step. If $a_k=1$ for all $k$, then I need $n$ steps. If $a_k=2$ for all $k$, then I need $n/2$ steps. In general, if $a_k=a$ for all $k$, then I need $n/a$ steps. But, if $a_k$ are arbitrary, how many steps are required? I guess it is $n/\min a_k$.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The number of steps is the minimum $k$ such that $a [1] + \cdots + a[k] \geq n$. The best upper bound which is oblivious to the contents of the array $a$ is $n$ (which is tight for an array filled by 1s). $\endgroup$ – Yuval Filmus Feb 13 '18 at 15:40
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael♦ Feb 13 '18 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.