4 edited title

# What is the complexity of How many operations does this algorithm require?

3 edited tags
2 added 28 characters in body

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

I have the following algorithm

x = 0
S = {}
while x + a[k] < n do
S = S + {k}
x = x + a[k]
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$$.

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

1