Need help determining Big O function to describe operation trip count

[KalEl]

I have done some searching on Google, and from what I understand, big O is referring to the magnitude of the trip count. In essence, it's an approximation of the trip count, not an exact value like done in most of your ordinary math classes, correct?

for ( j=0; j < n; j++ ) 
{
    for ( k=0; k <= j; k++ )
        A[j] = A[j] + C[k]*B[j];
}
 

so what exactly is the bigO for that code block? the outer loop runs N times. The inner loop runs J + 1 times, right? Since k = 0 and k <= to J, not < J.
then, J runs N times. So would it be something like N*N+1? I'm totally confused. any help would be much appreciated!

[ValValVal]

In the program inner loop runs times depending on the outer loop.

for ( j=0; j < n; j++ )  
{ 
    for ( k=0; k <= j; k++ ) 
        A[j] = A[j] + C[k]*B[j]; 
} 

When it runs in 1st outer loop it runs 1 time, in 2nd- 2 times in 3rd- 3 times.
So we can sum up the amount of time the expression

   A[j] = A[j] + C[k]*B[j]; 

will be run is

1+2+3+...+n
which is sum of arithmetical progression.
It equals n(1+n)/2 =(n*n+n)/2

so my guess big O of A[j] = A[j] + C[k]*B[j]; is (n*n+n)/2.

hope it helps,
Val

[JosAH]

@ValValVal
Which boils down to a big-Oh of n^2 (just take the factor with the highest exponent).

kind regards,

Jos

[KalEl]

Okay I see what you did there, but I don't understand the division of two. Is that because there are two loops nested in one another? If so, I think I get it, thanks alot! Appreciate it if you could clear this up as well.

Thanks a bunch and happy turkey day!

[ValValVal]

No it is just that to calculate
1+2+3+...+n
I looked up handy formula
S(n elements of arithmetical progression)=n* (1+n)/2

Good Turkey Day,
Val

[JosAH]

@KalEl
You want to add 1+2+3+ ... + n; assume n == 6 for example; the following figures show those numbers twice, one with asterisks and another one with capital Os. Combine those two figures: you have 6*7 == 42 symbols which is twice what you needed, so when you want to add 1+2+3+4+5+6 you have 6*7/2 == 21 symbols. In general when you add 1+2+3 ... n you have (n*(n+1))/2 == (n*n+n)/2 symbols.

               *
            *  *
         *  *  *
      *  *  *  *
   *  *  *  *  *
*  *  *  *  *  *
 
 
O  O  O  O  O  O
O  O  O  O  O
O  O  O  O 
O  O  O
O  O
O
 
 
O  O  O  O  O  O
O  O  O  O  O  *
O  O  O  O  *  *
O  O  O  *  *  *
O  O  *  *  *  *
O  *  *  *  *  *
*  *  *  *  *  *
 

kind regards,

Jos