CODEWITHSUNDEEP
algorithmbig-o
DashControl
DashControl

Reputation: 284

derivation of algorithm complexity

Refreshing up on algorithm complexity, I was looking at this example:

int x = 0;
     for ( int j = 1; j <= n; j++ )
        for ( int k = 1; k < 3*j; k++ )
             x = x + j;

I know this loops ends up being O(n^2). I'm believing inner loop is executed 3*n times( 3(1+2+...n) ), and the outer loop executes n times. So, O(3n*n) = O(3n^2) = O(n^2).

However, the source I'm looking at expands the execution of the inner loop to: 3(1+2+3+...+n) = 3n^2/2 + 3n/2. Can anyone explain the 3n^2/2 + 3n/2 execution times?

Upvotes: 0

Views: 144

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

The exact precision of your algorithm can be found using Sigma notation like this:

enter image description here

It's been empirically verified.

Upvotes: 1

Iłya Bursov
Iłya Bursov

Reputation: 24146

for each J you have to execute J * 3 iterations of internal loop, so you command x=x+j will be finally executed n * 3 * (1 + 2 + 3 ... + n) times, sum of Arithmetic progression is n*(n+1)/2, so you command will be executed:

3 * n * (n+1)/2 which is equals to (3*n^2)/2 + (3*n)/2

but big O is not how much iterations will be, it is about assymptotic measure, so in expression 3*n*(n+1)/2 needs to remove consts (set them all to 0 or 1), so we have 1*n*(n+0)/1 = n^2

Small update about big O calculation for this case: to make big O from the 3n(n+1)/2, for big O you can imagine than N is infinity, so:

infinity + 1 = infinity
3*infinity = infinity
infinity/2 = infinity
infinity*infinity = infinity^2

so you after this you have N^2

Upvotes: 1

digital_revenant
digital_revenant

Reputation: 3324

Big O notation gives an upper bound on the asymptotic running time of an algorithm. It does not take into account the lower order terms or the constant factors. Therefore O(10n2) and O(1000n2 + 4n + 56) is still O(n2).

What you are doing is try to count the number the number of operations in your algorithm. However Big O does not say anything about the exact number of operations. It simply provides you an upper bound on the worst case running time that may occur with an unfavorable input.

Upvotes: 1

dmm
dmm

Reputation: 495

The sum of integers from 1 to m is m*(m+1)/2. In the given problem, j goes from 1 to n, and k goes from 1 to 3*j. So the inner loop on k is executed 3*(1+2+3+4+5+...+n) times, with each term in that series representing one value of j. That gives 3n(n+1)/2. If you expand that, you get 3n^2/2+3n/2. The whole thing is still O(n^2), though. You don't care if your execution time is going up both quadratically and linearly, since the linear gets swamped by the quadratic.

Upvotes: 1

Related Questions