# How many operations does this algorithm require?

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

• The number of steps is the minimum $k$ such that $a  + \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). – Yuval Filmus Feb 13 '18 at 15:40
• 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! – Raphael Feb 13 '18 at 16:21