4 edited title
| link

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

3 edited tags
| link
2 added 28 characters in body
source | link

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
source | link