CODEWITHSUNDEEP
algorithmloopsfor-loopbig-oasymptotic-complexity
user2110714
user2110714

Reputation:

Running time of the following loop

I am trying to find the running time of the following loop:

int m=1;
for(i=1;i<=k;i++)
{
    for(j=1;j<=A[i];j++)
    {
        B[m]=i;
        m++;
     }
}

Here, A is an array keeping integers in it, and the sum of these integers is n. For example, if the length of A is 2, and A[1]=2 and a[2]=4, then inner loop will run 6 times.

So, in my lecture notes, it says the running time of this piece of code is O(n+k). But assume, for example, that k is 5, and length of array A is 4, and A[1]=3, A[2]=0, A[3]=0, A[4]=9, A[5]=0. So, n=12. Then, for k=1, inner loop will iterate 2 times, for k=2 the outer loop will iterate 1 time, for k=3 the outer loop will run 1 time, for k=4 the inner loop will run 9 times and for k=5 the outer loop will run 1 time, so total of iterations is 14. This is greater than both k and n, and running time is neither O(n) nor O(k). What am i doing wrong here?

Thank you

Upvotes: 2

Views: 235

Answers (2)

Thomas
Thomas

Reputation: 243

Unless I'm missing something the original function can be simplified to :

for(i=1;i<=k;i++) {
    for(j=1;j<=A[i];j++) {
     ... 
     }
}

In the worst case, sum(A[i]) = n

It seems to me this function should run no worse than k*n and for large k, k=n so O(n^2) should be the answer.

I think multiplication is in order, not addition.

Suppose loop A runs 3 times and loop B runs 2 times for each run of A. That equals 6 runs, not 5. So 3*2 rather than 3+2

Edit:

Proof:

f(n) = k*n

Let g(n) = n^2

f(n) <= C x g(n)

for C = 1, N0 = max(A[i])

Upvotes: 0

abeln
abeln

Reputation: 3759

The outer loop will iterate k times, because you're doing

for(i=1;i<=k;i++)

The total number of iterations of the inner loop is

sum (A[i]) for i = 1...k, which you know is = n.

That gives n + k iterations. Since the stuff inside the inner loop runs in constant time, the complexity is O(n + k).

EDIT:

What do we mean when we say that a non-negative function f(n) is O(g(n))?

Answer:

Look up the appropriate Stackoverflow question

What is a plain English explanation of "Big O" notation?

EDIT2:

Actually, the answers in the link above are quite verbose, so for the sake of completeness, here's the mathematical definition.

Let f(n) be a non-negative function. Then we say f(n) = O(g(n)) (read "f(n) is big-oh of g(n)") if there exist positive constants c and n0 such that

f(n) <= c g(n)

for all n >= n0.

Upvotes: 3

Related Questions