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 exp开发者_JAVA技巧lanation but please help me about these questions)
Thanks as advance...
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?
精彩评论