Not Yet Answered # Comlexity of algorithm

~s.o.s~ 2,560 Discussion Starter Laiq Ahmed 42 Infarction 503 Hey, so I wanna ask how I need to create a method who will remove word if in that word is 2 same chars. Example: "Potato" in this word there is a 2 "o" chars so this word will need to be removed. "Forum" in this word there is no ...

Hi I'm having a problem implementing a mini shopping cart drop down in the header to show the user all the products they have in their shopping cart. It seems the only solution for this is Ajax, and I've looked all over and can't find anything that I could possibly ...

0

Try out this simple code snippet:

```
int main (void)
{
const int LIMIT = 4 ;
int counter_I = 0, counter_J = 0, counter_K = 0 ;
int i, j, k ;
for ( i = 0; i < LIMIT; ++ i )
{
++ counter_I ;
for ( j = 0; j <= i; ++ j )
{
++ counter_J ;
for ( k = 0; k <= j ; ++ k )
{
++ counter_K ;
}
}
}
printf ( "\nThe value of counter i is %d ", counter_I ) ;
printf ( "\nThe value of counter j is %d ", counter_J ) ;
printf ( "\nThe value of counter k is %d ", counter_K ) ;
printf ( "\nThe value of counter is %d ", counter_I + counter_J + counter_K ) ;
return 0 ;
}
```

Thus the total times is:

Outermost loop = 4

Middle Loop = 4 + 6

InnerMost loop = 4 + 6 + 10

Hope you see the pattern.

0

Thank You ~S.o.S~ & Ancient Dragon for your help finally i learn how to calculate the polynomial complexity.....

```
for( int i=0; i<n; ++i )
for( int j=0; j<i; ++j )
printf("Hello World");
```

if we consider the inner loop the complexity ...

In the above loop int i=0; is an atomic statement which executes O(1) time i.e. constant time.

i<n executes (n+1) times

++i executes (n+1) times

printf(“Hello World”); //executes n times

so the total complexity is 1 + (n+1) + (n+1) + n = 3n+3

and the complexity of the ourter loop would be ...

For(int i=0; i < n; ++i )

{

//something executes 3n+3 times………….

}

lets examine the outer loop,

int i=0; //executes 1 time

i < n; //executes n+1 times\

++i //executes n+1 times.

And last the body executes ?? interesting………….

See………….

First i=0;

Complexity of body is 3(0)+3

i=1

Complexity of body is 3(1)+3

i=2

Complexity of body is 3(2)+3

i=3

Complexity of body is 3(4)+3

………………………………

……………………………….

i=n

Complexity of body is 3(n)+3

Therefore, total complexity is equal to

1 + (n+1) + (n+1) + [ {3(0)+3} + {3(1) + 3} + ………… + { 3(n) + 3} ]..

1 + (n+1) + (n+!) + [3(0 + 1 + 2 + 3 + … + n) + 3n] //using 1 + 2 + … + n = n(n+2)/2

1 + (n+1) + (n+1) + [3(n(n+2)/2) + 3n]

1 + (n+1) + (n+1) + 3n + 3(n(n+1)/2)

so, total complexity after solving……..

3 + 5n + 3n2/2 + 3n/2 ...............:p , hope i understand the mathematics behind ,...................

m i right gurus?

0

No. Unless 3n2/2 is supposed to mean (3n^2)/2, which is something of a deduction...

Let's work this out from the inside out, starting with `printf("Hello World");`

. This'll execute in (approx.) constant time.

Now we've got a loop. This loop will execute i times (0 to i-1). For each iteration of the loop, we'll execute the inner statement, which we noted is constant. Overall our time is a linear function of i, which we'll approximate as being i and drop anything else.

Now we've got another loop. This loop will execute n times, coincidentally providing the limit for the inner loop. The maximum limit for the inner loop is also n, and we'll use this in a second. So the outer loop executes n times, and for each iteration of that loop the inner one will execute as well, according to its own conditions. We can approximate that the inner loop will execute n times for each iteration of the outer loop. So, for each iteration of the outer loop, there's n iterations of the inner loop. There's n iterations of the outer loop. That's a total of n^2 iterations of the printf(), which would be O(n^2) in big-O notation. If you need the exact complexity, you'll have to work through it again tracking the details.

**Isn't it about time forums rewarded their contributors?**

Contribute to this discussion and earn rewards points that can be cashed out for dollars.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. Im using vb 2010. I want to dynamically add textboxes to my form by clicking on a button. I've google searched and so far this code worked:

```
Private Sub btn_addline_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btn_addline.Click
Dim txtB1 As New TextBox
Dim i
For i = ...
```