2

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

  • Remember that O(n+k) doesn't mean that it runs for _exactly_ n+k times. Also, O(n+k) is greater than O(n) or O(k). Finally, in your example, the length of array A seems to be 5, not 4. – Ted Hopp Mar 22 '13 at 19:26
  • Yes, i know. But i am not sure about the following: does O(n+k) is the same with O(n)+O(k)? Do both mean that it will run at most n or k times? –  Mar 22 '13 at 19:28
  • 1
    Not at most, "order of". – pamphlet Mar 22 '13 at 19:28
  • "and the sum of these integers is n" sure???? or did you mean the number of elements in the array is n – AlexWien Mar 22 '13 at 19:31
  • I don't understand. In your explanation, how can you have the length of array as 4 and have 5 elements in it? – noMAD Mar 22 '13 at 19:32
  • @AlexWien no, i mean the sum of these integers. For example if A[1]=4 and A[2]=6, then i say n=10 –  Mar 22 '13 at 19:32
  • @AlexWien: No, the sum is n seems right. In the worst case, the inner loop is run A[1] + A[2] + ... + A[k] = n times. – Knoothe Mar 22 '13 at 19:32
  • The notation O(n)+O(k) doesn't make any sense. Think about the definition of O(): f(x) = O((g(x)) iff there exists a positive constant M and an x0 such that f(x) <= M|g(x)| for all x >= x0. What would "O(n) + O(k)" mean? – Ted Hopp Mar 22 '13 at 19:33
  • @TedHopp: `O(f) + O(g)` certainly makes sense. For example, I could say that `O(f) + O(g) = O(max(f, g))`, where `h = max(f, g)` is such that `h(i) = max(f(i), g(i))`. In general, using `O` notation in the left hand side of an equation can be understood as meaning "for all functions that are `O(f)` and `O(g)`, then ... right hand side holds". This shows up in the literature all the time (see e.g. the CLRS book). – abeln Mar 22 '13 at 19:36

2 Answers2

3

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.

Community
  • 1
  • 1
abeln
  • 3,749
  • 2
  • 22
  • 31
  • Thanks, i think i am confused with the big O notation. I found the same number of iterations as you found, but i am not sure about how to express it in terms of bigO notation. For example, why don't we say that it is O(n)+O(k), but we say it is O(n+k)? What does O(n+k) mean verbally? Does it mean it will run at most n+k times? –  Mar 22 '13 at 19:31
  • @YasinRazlık - Regarding O(n+k) vs. O(n) + O(k), see my last comment to your original question. – Ted Hopp Mar 22 '13 at 19:34
0

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])

Thomas
  • 223
  • 1
  • 2
  • 7