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