Algorithm Analysis: Big O.... i think?

[G G]

O(log n) < O(n) < O(nLog n) < O(n^2) < O(n^3) < O(2^n) in running time.
2 2


my question has to do with actually determining that Big-O type.

Questions:

n represents the number of data items?

given a loop:
for (int i =0; i<1000: i++)
{
int a = a + i;
}
this would be a O(n), because as the number of items increases the time
to run increase linearly?

what about:
for ( int i=0: i<1000: i++)
{
int a = a + i;
int t = t + i;
}
are we only concerned of the number of item or will the two assignment
statement change the analysis in some way?

what about:

for (int i =0; i <1000; i++)
{
for ( int t =1; i < 1000; i++)
{
int a = a+i+t;
}
}

is this O(n^2)? why? how do you come up with that?

what are example of something being O(n/2), or O(log n )?
2

and how do you know that they are that?

 

[Eric Sosman]

O(log n) < O(n) < O(nLog n) < O(n^2) < O(n^3) < O(2^n) in running time.
2 2


my question has to do with actually determining that Big-O type.

... hence, not much to do with the C programming language.
A forum like comp.programming might be better suited for questions
about programming in general, as opposed to questions about
programming in a particular language or in a particular environment.

 

[Ben Bacarisse]

O(log n) < O(n) < O(nLog n) < O(n^2) < O(n^3) < O(2^n) in running time.
2 2

Use a fixed-width font if you want to write subscripts that way, but
people will understand log2(n) just as well (and, in any case, the base
does not matter!).

my question has to do with actually determining that Big-O type.

This belongs in comp.programming. Rather than my setting follow-ups
(which does not always work) I strongly encourage you to post again
there.

<snip>

 

[G G]

ok

 

[G G]

ok

Please don't not discuss, post, here. Ben tells me this is a really not the proper place for this discussion.

He gave me a proper spot to post. I have posted this question over on comp.programming

thanks everyone,

g.