CODEWITHSUNDEEP
big-o
Gokhan Gumus
Gokhan Gumus

Reputation: 21

I need help for Calculating "Big O"

the first problem;

sum = 0;

for i = 1 to n; i++
 {   
 for j = 1 to i * i; j++
    {
    for k = 1 to j; k++
       sum ++;
    }
 }

and the

Second problem;

sum = 0;

for i = 1 to n
  {  
  for j = 1 to i * i
    {
    if j mod i == 0
      {  
      for k = 1 to j
           sum ++;
      }
    }
  }

Hi I am new in IT and I need a help (actually two :D )

I met with "big o" few days before and while I was studying about it I found this address, and actualy I learn manythings from here...

but most of the examples about "big o" were just for explaining it, here I have two questions. After my calculations I found the big o for the first one as O(n^5) and for the second one O(n^3). but these values were too huge...

therefore I am here, I need your help... (even you can write what ever the result is without explanation but please help me about these questions)

Thanks as advance...

Upvotes: 2

Views: 373

Answers (1)

Charlie Martin
Charlie Martin

Reputation: 112404

Okay, the definition of big-O is that a function g(x) is O(f(x)) if g(x) ≤ kf(x) for some constant k.

In other words, big-O tells you some idea of how fast a function grows; if it's $O(n)* it grows proportional to the length of the input. What you're counting, and details of the computation, are hidden in the constant.

Here's some examples:

for i from 1 to n {
  do something 
}

is O(n). You go through the n items once each.

for i from 1 to n {
}
for i from 1 to n {
}

twice in sequence is still O(n), because you're looking at each of the n items twice. That's 2n which is still O(n).

On the other hand,

for i from 1 to n {
   for j from 1 to n {

   }
 }

is O(n2) because for each step of i, you go through 1-n for j.

Straighten out the indentation of your code so we're sure what you're doing, and see if those examples help.

Update

These are pretty amusing questions, come to think of it.

  • the i*i term

Consider what the values of i*i, ie, i2 will be. At worst, i==n and so j is 1,4,9,16...(n*n). What's the sum of x2 for x from 1 to n? (Hint: 1/6(...)(...), now you fill in the blanks.)

  • the if ... mod term

when will that term be true?

Upvotes: 2

Related Questions