Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3721 > unrolled thread

algorithm analysis Big-O

Back to article view | Back to comp.programming

Contents

  algorithm analysis Big-O gdotone@gmail.com - 2013-09-14 06:32 -0700
    Re: algorithm analysis Big-O Johann Klammer <klammerj@NOSPAM.a1.net> - 2013-09-14 16:50 +0200
    Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-14 08:45 -0700
    Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-14 12:29 -0400
      Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-14 11:12 -0700
        Re: algorithm analysis Big-O Willem <willem@turtle.stack.nl> - 2013-09-14 19:21 +0000
          Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-14 23:12 -0400
            Re: algorithm analysis Big-O Willem <willem@turtle.stack.nl> - 2013-09-15 08:16 +0000
              Re: algorithm analysis Big-O Richard Damon <Richard@Damon-Family.org> - 2013-09-22 19:04 -0400
                Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-23 02:32 +0100
            Re: algorithm analysis Big-O malcolm.mclean5@btinternet.com - 2013-09-17 15:07 -0700
      Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 20:27 +0100
      Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-15 18:09 +0000
        Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 20:47 +0100
          Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-15 20:42 +0000
            Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-16 00:56 +0100
              Re: algorithm analysis Big-O blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2013-09-19 20:26 +0000
    Re: algorithm analysis Big-O Öö Tiib <ootiib@hot.ee> - 2013-09-14 11:08 -0700
    Re: algorithm analysis Big-O Robert Wessel <robertwessel2@yahoo.com> - 2013-09-14 13:43 -0500
    Re: algorithm analysis Big-O Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:01 +0100

#3721 — algorithm analysis Big-O

O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
                                       
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 )?   

and how do you know that they are that? 
  
i have been reading some of the post, in other groups, and posters discuss the speed of the code or 
the speed of the algorithm.
Can you recommend a book or several books that discuss algorithm analysis,
 with plenty of examples?

thanks, 

g.
    

[toc] | [next] | [standalone]

#3722

gdotone@gmail.com wrote:
> O(log  n)<  O(n)<  O(nLog  n)<  O(n^2)<  O(n^3)<  O(2^n) in running time.
>
> 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?
Yes
>
> 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?
>
I believe this is still O(n)
Same as this:
for ( int i=0: i<1000: i++)
{
   int a = a + i;
}
for ( int i=0: i<1000: i++)
{
   int t = t + i;
}



> 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?
No, also O(n)
the inner loop also uses i variable
perhaps you meant to write:

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

(replace i in second loop with t)?
'cause then it was O(n^2)
>
> what are example of something being O(n/2), or O(log  n )?
I believe binary search(in sorted array) is O(log n)...
the array gets split in the middle at each step
then repeat for one half...
I believe there is no O(n/2).
it's the same as O(n).
O notation is supposed to give an upper bound
regardless of constant multiplicative factors or added
constants so that the runtime t(n) of an algorithm with
O(f(n))
t(n) <= k1*f(n)+k2
for all input sizes n
for n/2
k1 is 1/2
so f(n) can still be n.

there is also a small o notation which
is similar except for:
t(n) >= k1*f(n)+k2
(it gives a lower boundary)

and a theta notation which requires the limit for
t(n) with n towards infinity to equal f(n)
lim(t(n))=f(n)
n->inf

...or something like that...
>
> and how do you know that they are that?
Usually you'll try to define the problem recursively,
then try to solve the recursions,
until you get a closed form, or you can guess an upper boundary...
An algorithm in O(log n) is also in O(n) and O(n^2), but you'll want to 
find the smallest limit...

>
> i have been reading some of the post, in other groups, and posters discuss the speed of the code or
> the speed of the algorithm.
> Can you recommend a book or several books that discuss algorithm analysis,
>   with plenty of examples?
>

Corman, Leiserson, Rivest, Stein
Introduction to Algorithms
Is pretty much standard...

> thanks,
>
> g.
>

disclaimer: the drivel above is mostly based on my understanding of that 
book, so take it with a grain of salt...

[toc] | [prev] | [next] | [standalone]

#3723

On Saturday, September 14, 2013 2:32:23 PM UTC+1, gdo...@gmail.com wrote:
> O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
> my question has to do with actually determining that Big-O type. 
>
> Questions: 
>  
> n represents the number of data items? 
> 
Normally, yes. N is the size of the problem, which is generally the number
of data items in a list that the algorithm operates on. But occasionally, e.g.
factorisation algorithms, N is an integer.
> 
> 
> 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? 
> 
the loop for(i=0;i<N;i++) is O(N), even if the loop body is empty.

the nested loops

for(i=0;i<N;i++)
  for(ii=0;ii<N;ii++)
  
are O(N^2)

and so on. They're doing N and N*N or N squared operations, even if they
are just increments and comparisons.
>
> Can you recommend a book or several books that discuss algorithm analysis,
>  with plenty of examples?
> 
Big(O) notation is quite simple once you get the hang of it. The hard part
is devising algorithms with lower big(O) representations than the naive or
strightforwards approaches.
Big(O) also applies to memory use, by the way, or to anything that scales
with increasing N. 

[toc] | [prev] | [next] | [standalone]

#3724

On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
> O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
>  

Only for n large.

It is quite possible for a O(2^n) algorithm to be much faster than a
O(log n) algorithm for small n, primarily because the purpose of the O()
notation is to look at scaling at large values of n.

When determining the O() value for an algorithm, you look at how much of
something (time, memory, or what ever) the algorithm uses as n
increases. At some point, the amount of that stuff that an O(x(n))
algorithm uses will be approximately k*x(n) for all n sufficiently
large. We ignore the k factor, as that becomes a function of the units
we are using, and as long as k is "reasonable" it doesn't normally
affect our decisions as to which algorithm to use. There can be cases
though, where n doesn't really get extremely large, where the the scale
factor may make a "larger" O() be better than the lower O(), or you need
to look at "smaller" growth terms as they have a significant scale
factor and there contribution isn't negligible.

[toc] | [prev] | [next] | [standalone]

#3726

On Saturday, September 14, 2013 5:29:34 PM UTC+1, Richard Damon wrote:
>  
> At some point, the amount of that stuff that an O(x(n))
> algorithm uses will be approximately k*x(n) for all n sufficiently
> large. We ignore the k factor, as that becomes a function of the units
> we are using, and as long as k is "reasonable" it doesn't normally
> affect our decisions as to which algorithm to use. There can be cases
> though, where n doesn't really get extremely large, where the the scale
> factor may make a "larger" O() be better than the lower O(), or you need
> to look at "smaller" growth terms as they have a significant scale
> factor and there contribution isn't negligible.
>
The other factor is that generally higher big(O) algorithms are more
straightforwards, intuitive, easy to understand, easy to write and to
check manually for correctness. That very often outweighs a saving in
machine time.

[toc] | [prev] | [next] | [standalone]

#3731

malcolm.mclean5@btinternet.com wrote:
) The other factor is that generally higher big(O) algorithms are more
) straightforwards, intuitive, easy to understand, easy to write and to
) check manually for correctness. That very often outweighs a saving in
) machine time.

I disagree.  For constant savings in machine time, I would agree with you,
but the consideration 'the dataset will never be very large' has turned
out to be false so often (with disastrous results) that I would never
rely on it.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#3735

On 9/14/13 3:21 PM, Willem wrote:
> malcolm.mclean5@btinternet.com wrote:
> ) The other factor is that generally higher big(O) algorithms are more
> ) straightforwards, intuitive, easy to understand, easy to write and to
> ) check manually for correctness. That very often outweighs a saving in
> ) machine time.
> 
> I disagree.  For constant savings in machine time, I would agree with you,
> but the consideration 'the dataset will never be very large' has turned
> out to be false so often (with disastrous results) that I would never
> rely on it.
> 
> 
> SaSW, Willem
> 
Sometimes, there is an upper limit in "size" imposed on the system by
things much harder to change than the software. In this sort of
environment I have no problems using a method that might not scale well
when far past the environmental limits. As an example, a system which
naturally has no mass store, assuming that all data will fit in
addressable ram is reasonable. Assuming that the amount of ram will be
fixed at the first design probably is not.

[toc] | [prev] | [next] | [standalone]

#3738

Richard Damon wrote:
) On 9/14/13 3:21 PM, Willem wrote:
)> I disagree.  For constant savings in machine time, I would agree with you,
)> but the consideration 'the dataset will never be very large' has turned
)> out to be false so often (with disastrous results) that I would never
)> rely on it.
)
) Sometimes, there is an upper limit in "size" imposed on the system by
) things much harder to change than the software. In this sort of
) environment I have no problems using a method that might not scale well
) when far past the environmental limits. As an example, a system which
) naturally has no mass store, assuming that all data will fit in
) addressable ram is reasonable. Assuming that the amount of ram will be
) fixed at the first design probably is not.

And then your code gets reused on a new embedded system with 16 times
the amount of RAM, and suddenly the orbital calculations take so long
that the capsule misses the burn window.

Of course, that will never happen because they will exhaustively test
the software on the new hardware... right?


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#3757

On 9/15/13 4:16 AM, Willem wrote:
> Richard Damon wrote:
> ) On 9/14/13 3:21 PM, Willem wrote:
> )> I disagree.  For constant savings in machine time, I would agree with you,
> )> but the consideration 'the dataset will never be very large' has turned
> )> out to be false so often (with disastrous results) that I would never
> )> rely on it.
> )
> ) Sometimes, there is an upper limit in "size" imposed on the system by
> ) things much harder to change than the software. In this sort of
> ) environment I have no problems using a method that might not scale well
> ) when far past the environmental limits. As an example, a system which
> ) naturally has no mass store, assuming that all data will fit in
> ) addressable ram is reasonable. Assuming that the amount of ram will be
> ) fixed at the first design probably is not.
> 
> And then your code gets reused on a new embedded system with 16 times
> the amount of RAM, and suddenly the orbital calculations take so long
> that the capsule misses the burn window.
> 
> Of course, that will never happen because they will exhaustively test
> the software on the new hardware... right?
> 
> 
> SaSW, Willem
> 

Note that my comment was on "natural" limits, not installed memory, so a
system that has 16 times the memory of the natural limit, would require
some form of paging like the ancient EMS memory system. To move a
program to such a system without a detailed analysis will have bigger
problems then being slow, it will run into problems of data no longer
being available when needed.

Moving from one platform to another with a significantly larger natural
limit and not asking your self the impact is sort of foolish.

Lets say that an O(n^2) algroithm was used instead of a O(n log n). For
a 16x increase in problem size, and assuming using log2, the previous
method would incure a 256x slow down, while the better algorith "only" a
64x slowdown. If the 256x catches you by surprize, so would the 64x.

I won't say that this doesn't happen, but it seems a bad design method
to intentionally use an algorithm that is slower in the range of sizes
you will be using it, to maybe avoid problems with moving the program to
a significantly different machine.

Much better is to clearly document the decision, and the reasons, and
let the future take care of itself. If you really want to be defensive,
add a precondition check that the problem is in the right range of
sizes, with documentation on why it is there. If a later programmer puts
the penny in the fuse, its on their head.

[toc] | [prev] | [next] | [standalone]

#3758

Richard Damon <Richard@Damon-Family.org> writes:
<snip>
Please excuse this side-rant.  I know it' not really about what you are
discussing, but I think it's a point worth making.

> Lets say that an O(n^2) algroithm was used instead of a O(n log n). For
> a 16x increase in problem size, and assuming using log2, the previous
> method would incure a 256x slow down, while the better algorith "only" a
> 64x slowdown. If the 256x catches you by surprize, so would the 64x.

Big O is not the right notation here.  I think you simply mean that one
algorithm is quadratic, and the other runs in time proportional to
n.log2(n).

If you use O(n^n), you run into two problems.  First (the technical
nit-pick one) the algorithm might be linear in run-time.  I know people
say O(n^n) to mean "and no better" but it still bugs me!  The second is
less technical.  The asymptotic performance does not say anything about
any two real run-times.  An algorithm that is quadratic in the long-run
might be much better than that over small values, so 16 times the
problem might not take 256 times the run-time.  Eventually, for large
enough n, you'll get that multiplier, but there is no saying when it
will kick in.

If you just say that the algorithm's run-time is proportional to n^n,
then you avoid both of these issues.

The other point is that (n*16).log2(n*16) / n.log(n) is not 64.  It's
not a constant at all, so even if the other algorithm's run-time is
exactly proportional to n.log2(n), you can't say how much slower a
problem of 16 times the size will be unless you specify n.  You can, in
fact, make the slow-down as close to 16 as you like by picking large
enough n values.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3747

On Sunday, September 15, 2013 4:12:35 AM UTC+1, Richard Damon wrote:
> On 9/14/13 3:21 PM, Willem wrote:
> 
> > malcolm.mclean5@btinternet.com wrote:
> 
> > ) The other factor is that generally higher big(O) algorithms are more
> > ) straightforwards, intuitive, easy to understand, easy to write and to
> > ) check manually for correctness. That very often outweighs a saving in
> > ) machine time.
> 
> 
> > I disagree.  For constant savings in machine time, I would agree with 
> > you, but the consideration 'the dataset will never be very large' has
> > turned out to be false so often (with disastrous results) that I would
> > never rely on it.
> 
> 
> Sometimes, there is an upper limit in "size" imposed on the system by
> things much harder to change than the software. In this sort of
> environment I have no problems using a method that might not scale well
> when far past the environmental limits. As an example, a system which
> naturally has no mass store, assuming that all data will fit in
> addressable ram is reasonable. Assuming that the amount of ram will be
> fixed at the first design probably is not.
>
An example would be an anagram function I included in my crossword
designer software 
http://sourceforge.net/projects/crossworddesign/?source=directory

it's O(N^2). But on random words it will normally return in O(N)
time. Both string length and the alphabet size can scale. If
the alphabet is fixed and small, there's an O(N) algorithm, the
histogram method. If the alphabet is potentially large you
can do it by sorting, which is O(N logN).
But both these algorithms would be overkill for that application.
It's meant to be used for single English words, which are rarely
more than ten letters.

[toc] | [prev] | [next] | [standalone]

#3732

Richard Damon <Richard@Damon-Family.org> writes:

> On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
>> O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
>
> Only for n large.

Actually the notation is reasonable.  O(f) is a set of functions, and <
can be read as set inclusion.  In fact < is sometimes used to mean
inclusion when its role as an ordering is paramount.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3739

In article <O90Zt.29906$sr1.508@en-nntp-04.dc1.easynews.com>,
Richard Damon  <Richard@Damon-Family.org> wrote:
> On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
> > O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
> >  
> 
> Only for n large.


Isn't that part of the def ....  Oh.  Well, maybe not exactly:
The formal definition of what it means for a function to be O(f(n))
does include a notion of "for sufficiently large n", but I'm not
finding, in a quick Web search, a formal definition of what 
"O(f(n)) < O(g(n))" means.  But I'm inclined to think that it's
something along the lines of "if function f1(n) is O(f(n)), and
function g1(n) is O(g(n)), then for sufficiently large n,
f1(n) < g1(n)".  Maybe someone who knows this off the top of
his/her head, or has the right books nearby, can fill in the
details.


> It is quite possible for a O(2^n) algorithm to be much faster than a
> O(log n) algorithm for small n, primarily because the purpose of the O()
> notation is to look at scaling at large values of n.


But this part I agree with!


> When determining the O() value for an algorithm, you look at how much of
> something (time, memory, or what ever) the algorithm uses as n
> increases. At some point, the amount of that stuff that an O(x(n))
> algorithm uses will be approximately k*x(n) for all n sufficiently
> large. We ignore the k factor, as that becomes a function of the units
> we are using, and as long as k is "reasonable" it doesn't normally
> affect our decisions as to which algorithm to use. There can be cases
> though, where n doesn't really get extremely large, where the the scale
> factor may make a "larger" O() be better than the lower O(), or you need
> to look at "smaller" growth terms as they have a significant scale
> factor and there contribution isn't negligible.


To the OP:  I don't have a specific book or other resource to recommend,
but a search term that may be useful is "analysis of algorithms".  


-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

[toc] | [prev] | [next] | [standalone]

#3740

blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:

> In article <O90Zt.29906$sr1.508@en-nntp-04.dc1.easynews.com>,
> Richard Damon  <Richard@Damon-Family.org> wrote:
>> On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
>> > O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
>> 
>> Only for n large.
>
> Isn't that part of the def ....  Oh.  Well, maybe not exactly:
> The formal definition of what it means for a function to be O(f(n))
> does include a notion of "for sufficiently large n", but I'm not
> finding, in a quick Web search, a formal definition of what 
> "O(f(n)) < O(g(n))" means.  But I'm inclined to think that it's
> something along the lines of "if function f1(n) is O(f(n)), and
> function g1(n) is O(g(n)), then for sufficiently large n,
> f1(n) < g1(n)".  Maybe someone who knows this off the top of
> his/her head, or has the right books nearby, can fill in the
> details.

With that meaning, neither O(1) < O(n) nor O(n) < O(1) would be true, so
if that is what was meant, it's not very useful.  The problem here is
that if f is O(1) it is also O(n).

That there is some confusion here is not surprising.  The exact meaning
of operators near a "big O" is often hard to determine.  For example,
some people write "g = O(f)", but whatever the "=" means, it certainly
isn't equality.  In other fields you'll see it "added":

  p(x) = x^5 + a.x^4 + O(x^2).

Again, that can't be normal addition.

One approach to formalising it is to say that O(f) is the set of all
functions, g, that have the property that |g(n)| < C.f(n) for some
constant C and all but a finite set of n.  (There are other ways to get
similar meanings -- there doesn't seem to be a universal definition.)

With this definition, O(f) is a real "thing" (just a set) and we can use
normal set operations on it.  For example, where many people write,
informally, "g = O(f)", we can now write "g in O(f)" using set
membership.  With this more formal definition, using less than
(especially in ASCII) as the subset relation is not unreasonable.  With
this meaning, O(n) < O(n^2) because all functions that are in O(n) are
also in O(n^2), whilst there are functions in O(n^2) that are not in
O(n).  (I'd use a Unicode "subset of" if that were not likely to derail
the thread with a discussion of non-ASCII postings.)

I like this approach, but it's not universal and it may even be a
minority view.  Some authors just think of O(f) as a shorthand for a
property (pronounced "order of f") and, if they are careful, they write
"g is O(f)".  If they are not so careful and write "g = O(f)" the "=" is
meant to be pronounced "is".  In this sort of informal context, I'd
guess that O(f) < O(g) means that all functions that are O(f) are also
O(g), and that there exists at least one function that is O(g) that is
not O(f).  However, this is derived from what I *want* it to mean,
rather than any guess at what the OP meant.

In complexity theory there are lots of sets of things with interesting
properties (decidable languages, P, NP and so on), so I think it makes
perfect sense to formalise O(f) as just another set of things with some
interesting property.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3741

In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>,
Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:
> 
> > In article <O90Zt.29906$sr1.508@en-nntp-04.dc1.easynews.com>,
> > Richard Damon  <Richard@Damon-Family.org> wrote:
> >> On 9/14/13 9:32 AM, gdotone@gmail.com wrote:
> >> > O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
> >> 
> >> Only for n large.
> >
> > Isn't that part of the def ....  Oh.  Well, maybe not exactly:
> > The formal definition of what it means for a function to be O(f(n))
> > does include a notion of "for sufficiently large n", but I'm not
> > finding, in a quick Web search, a formal definition of what 
> > "O(f(n)) < O(g(n))" means.  But I'm inclined to think that it's
> > something along the lines of "if function f1(n) is O(f(n)), and
> > function g1(n) is O(g(n)), then for sufficiently large n,
> > f1(n) < g1(n)".  Maybe someone who knows this off the top of
> > his/her head, or has the right books nearby, can fill in the
> > details.
> 
> With that meaning, neither O(1) < O(n) nor O(n) < O(1) would be true, so
> if that is what was meant, it's not very useful.  The problem here is
> that if f is O(1) it is also O(n).

Indeed.  What was I thinking ....  (*WAS* I thinking .... )  


> That there is some confusion here is not surprising.  The exact meaning
> of operators near a "big O" is often hard to determine.  For example,
> some people write "g = O(f)", but whatever the "=" means, it certainly
> isn't equality.  In other fields you'll see it "added":
> 
>   p(x) = x^5 + a.x^4 + O(x^2).
> 
> Again, that can't be normal addition.
> 
> One approach to formalising it is to say that O(f) is the set of all
> functions, g, that have the property that |g(n)| < C.f(n) for some
> constant C and all but a finite set of n.  (There are other ways to get
> similar meanings -- there doesn't seem to be a universal definition.)
> 
> With this definition, O(f) is a real "thing" (just a set) and we can use
> normal set operations on it.  For example, where many people write,
> informally, "g = O(f)", we can now write "g in O(f)" using set
> membership.  With this more formal definition, using less than
> (especially in ASCII) as the subset relation is not unreasonable.  With
> this meaning, O(n) < O(n^2) because all functions that are in O(n) are
> also in O(n^2), whilst there are functions in O(n^2) that are not in
> O(n).  (I'd use a Unicode "subset of" if that were not likely to derail
> the thread with a discussion of non-ASCII postings.)
> 
> I like this approach, but it's not universal and it may even be a
> minority view.  Some authors just think of O(f) as a shorthand for a
> property (pronounced "order of f") and, if they are careful, they write
> "g is O(f)".  If they are not so careful and write "g = O(f)" the "=" is
> meant to be pronounced "is".  In this sort of informal context, I'd
> guess that O(f) < O(g) means that all functions that are O(f) are also
> O(g), and that there exists at least one function that is O(g) that is
> not O(f).  However, this is derived from what I *want* it to mean,
> rather than any guess at what the OP meant.
> 
> In complexity theory there are lots of sets of things with interesting
> properties (decidable languages, P, NP and so on), so I think it makes
> perfect sense to formalise O(f) as just another set of things with some
> interesting property.
> 

"Couldn't snip a word" ?

Thanks -- this is pretty much the meaning I think I would have had
in mind if I'd been thinking clearly.  :-)??  I like your set-based
definition, but defining O(f(n)) as a property seems plausible too
(and then you could convey the "<" idea using implication?  i.e., if
a function has property O(f(n) it also has property O(g(n))?).


-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

[toc] | [prev] | [next] | [standalone]

#3742

blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:

> In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>,
> Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
<snip>
>> One approach to formalising it is to say that O(f) is the set of all
>> functions, g, that have the property that |g(n)| < C.f(n) for some
>> constant C and all but a finite set of n.
<snip>
>> ... Some authors just think of O(f) as a shorthand for a
>> property
<snip>
> ...  I like your set-based
> definition, but defining O(f(n)) as a property seems plausible too
> (and then you could convey the "<" idea using implication?  i.e., if
> a function has property O(f(n) it also has property O(g(n))?).

Yes, though the zealot in me (see below) leans toward using <= for the
meaning of that implication.

The distinction between a set and the property that defines membership
is not one that would bother many mathematicians.  In fact, notation is
often successful when it forms a kind of mathematical metaphor, rather
than encapsulating an exact meaning.  Look how dy/dx displaced f-with-a-
dot-over-it, probably because of what the division suggests despite
being, formally, meaningless.  You can even pretend that dy/dx really is
a fraction and still get the right answer in some circumstances.  I
think there's a lot of that kind of thing going on with the various ways
in which O(f) is used.

There's a great book about what mathematics really is called The
Mathematical Experience by Davis and Hersh.  In one chapter, they review
the more than 2000 years of presenting the Chinese remainder theorem.
One example is "in the hands of a contemporary computer scientist":

  If n = p1^a1.p2^a2...pr^ar is the decomposition of the integer n into
  distinct prime powers: pi^a1 = qi, then the cyclic group Zn has the
  product representation

       Zn ~= Zq1 x Zq2 x ... x Zqr.

They then make a remark that has stayed with me for decades:

  "... it is true that computer science in its theoretical formulation
  is dominated by a spirit of abstraction which defers to no other
  branch of mathematics in its zealotry."

Though it can be seen as a little snide, I like to think of it as both a
warning and a commendation.  Though I am no theoretical computer
scientist I do have "tendencies" which I try to keep in check by
bearing this remark in in mind.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#3751

In article <0.8be74675a3c51fd4b4c6.20130916005604BST.87d2o9tzaj.fsf@bsb.me.uk>,
Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> writes:
> 
> > In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>,
> > Ben Bacarisse  <ben.usenet@bsb.me.uk> wrote:
> <snip>
> >> One approach to formalising it is to say that O(f) is the set of all
> >> functions, g, that have the property that |g(n)| < C.f(n) for some
> >> constant C and all but a finite set of n.
> <snip>
> >> ... Some authors just think of O(f) as a shorthand for a
> >> property
> <snip>
> > ...  I like your set-based
> > definition, but defining O(f(n)) as a property seems plausible too
> > (and then you could convey the "<" idea using implication?  i.e., if
> > a function has property O(f(n) it also has property O(g(n))?).
> 
> Yes, though the zealot in me (see below) leans toward using <= for the
> meaning of that implication.
> 
> The distinction between a set and the property that defines membership
> is not one that would bother many mathematicians.  In fact, notation is
> often successful when it forms a kind of mathematical metaphor, rather
> than encapsulating an exact meaning.  Look how dy/dx displaced f-with-a-
> dot-over-it, probably because of what the division suggests despite
> being, formally, meaningless.  You can even pretend that dy/dx really is
> a fraction and still get the right answer in some circumstances.  I
> think there's a lot of that kind of thing going on with the various ways
> in which O(f) is used.


I'm not sure I completely understand what you're getting at here, but
if you want to say that "<=" means different things in different contexts
(sometimes numeric inequality, sometimes some other kind of ordering,
possibly a partial ordering), and that it's best to be clear what it
means in a given context -- yes, I agree.


> There's a great book about what mathematics really is called The
> Mathematical Experience by Davis and Hersh.  In one chapter, they review
> the more than 2000 years of presenting the Chinese remainder theorem.
> One example is "in the hands of a contemporary computer scientist":
> 
>   If n = p1^a1.p2^a2...pr^ar is the decomposition of the integer n into
>   distinct prime powers: pi^a1 = qi, then the cyclic group Zn has the
>   product representation
> 
>        Zn ~= Zq1 x Zq2 x ... x Zqr.
> 
> They then make a remark that has stayed with me for decades:
> 
>   "... it is true that computer science in its theoretical formulation
>   is dominated by a spirit of abstraction which defers to no other
>   branch of mathematics in its zealotry."
> 
> Though it can be seen as a little snide, I like to think of it as both a
> warning and a commendation.  Though I am no theoretical computer
> scientist I do have "tendencies" which I try to keep in check by
> bearing this remark in in mind.
> 


The authors have a more math-positive view of computer science than at
least one practicioner, then.  (Though how nice if they are right!)
A favorite quote of mine (not because I necessarily agree, but 
because -- I'm not sure I can articulate why!)

"Computer scientists are more willing to explore unconventional
proof styles. Unfortunately, I have found that few of them
care whether they have published incorrect results. They often
seem glad that an error was not caught by the referees, since that
would have meant one fewer publication. I fear that few computer
scientists will be motivated to use a proof style that is
likely to reveal their mistakes. Structured proofs are unlikely
to be widely used in computer science until publishing incorrect
results is considered embarrassing rather than normal."

-- ``How to Write a Proof,'' Leslie Lamport,
	DEC SRC Research Report 94, February 14, 1993.

On the other side, maybe, there's Edsger Dijkstra, who, if I remember
right, in one of his books explains the somewhat unconventional proof
style *he* uses, in a way that seems to connote that he knows how to
present proofs better than mathematicians.  I think it's in the same
section where he says something about punctuation that has the same
connotation about experts in that field.  Well, he was well-known
for having strong and sometimes unconventional opinions.  :-)?
And in both cases IIRC he did have a point!

-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

[toc] | [prev] | [next] | [standalone]

#3725

On Saturday, 14 September 2013 16:32:23 UTC+3, gdo...@gmail.com  wrote:
> O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
>
> my question has to do with actually determining that Big-O type. 
> 
> Questions: 
> 
> n represents the number of data items? 

Usually it is said what count that 'n' (or 'n' and 'm' in 'O(n*m)') is. If 
it is omitted then it is assumed to be obvious.

> 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? 

Just a nitpick but since others have answered to what you meant I will 
answer to what you wrote.

If this is a C or C++ program (and semicolon was meant after 1000 instead
of colon) then technically is more correct to call it 'O(0)' since I do 
not have any C or C++ compilers that do not optimize that code entirely 
out. The same problem is with rest of your examples. All algorithms should
have input and output and the input should affect output, otherwise the
algorithm does nothing (can be discarded).

[toc] | [prev] | [next] | [standalone]

#3729

On Sat, 14 Sep 2013 06:32:23 -0700 (PDT), gdotone@gmail.com wrote:

>O(log  n)  < O(n)  < O(nLog  n)  < O(n^2)  < O(n^3)  < O(2^n) in running time. 
>                                       
>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? 


Actually both of those are O(1) - they run in constant time.

If, OTOH, you had:

  for(i=0; i<n; i++)
    {
    ...work...
    }

  for(i=0; i<n; i++)
    {
    for(j=0; j<n; j++)
      {
      ...work...
      }
   }

Those would be O(n) or O(n**2), respectively.

If the inner loop had a different quantity of items to process:

  for(i=0; i<n; i++)
    {
    for(j=0; j<m; j++)  /* note 'm' */
      {
      ...work...
      }
   }

it would usually be described as O(n*m).


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


You'd never have O(n/2), the constant factor is always ignored.  IOW,
from a Big-Oh standpoint:

  for(i=0; i<n; i++)
    {
    ...a tiny bit of work...
    }

and:

  for(i=0; i<n; i++)
    {
    ...lots and lots and lots of work...
    }

Are both exactly O(n), even though the second would obviously have a
much longer runtime.

As for some of the other common classes, binary search is O(log n),
and Heapsort is O(n * (log n)).  Note that Quicksort, in the common
case, is also O(n log n), but is typically about twice as fast sorting
things as Heapsort is.

And usually only the "biggest" term counts.  So if you had:

  for(i=0; i<n; i++)
    {
    for(j=0; j<n; j++)
      {
      ...work...
      }
   }
  for(i=0; i<n; i++)
    {
    ...some other work...
    }

Which could be described as O(n**2 + n), that would usually just be
O(n**2).


>and how do you know that they are that? 


Conceptually you're just estimating how the work done by the algorithm
grows with the size(s) of the input.  You can even do that
empirically, just by running with a bunch of different sized inputs,
putting a counter into the middle of the algorithm, graphing the
results, and then picking a curve to fit.  Much more commonly we do it
analytically, by looking at known patterns (we know a loop is O(n), a
binary search is O(log n)), and nestings and combinations of those
things.  It can get quite tricky when there are dependencies between
the different bits - even something as simple as Shellsort doesn't
have a fully developed understanding of its runtime in the general
case (although for many choices of decrement, it does).

[toc] | [prev] | [next] | [standalone]

#3734

gdotone@gmail.com writes:

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

Provided you understand O(f) as being a set of functions and < as set
inclusion, then yes.  As other have pointed out, a quadratic algorithm
could beat a linear on in some cases.
                                        
> my question has to do with actually determining that Big-O type. 
>
> Questions: 
>
> n represents the number of data items? 

Formally, it's just the size of the input.  That can be a very slippery
concept.  Binary search is often described as being Olog(n)), but I can
make a search algorithm do more and more work by giving it the same
number of items, but bigger and bigger ones.

The moral of this is that *you* need to specify what n is.  For binary
search, you might be interested in the number of items, of you might be
interested in the total size of the input.  Which you choose depends on
what aspect the algorithm you want to highlight.

When doing formal complexity analysis, n is the total size of the input
in whatever model of computing is being used.  With Turning machines, it
would be the number of consecutive non-blank locations on the initial
tape.  This can make it much more complicated.  You can't, for example,
just assume that multiplication happens in a single "beat" --
multiplying big numbers is slower then multiplying small ones...

> 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? 

This brings me to another key point.  You must also state what is being
measured.  Just saying "time" is often too vague.  Assuming you meant n
where you wrote 1000, the above is only linear if addition, assignment,
and comparison are linear themselves.  In fact, you can assume that's
true, but it might not be if you'd written a * i.

What people generally do to avoid this complexity is to say something
like "the above is O(n) in terms of addition operations, where n is the
number of loop executions".

This means you can use O notation when it does not mean time in any
practical sense.  Lets say you have an algorithm that involves some
number of matrix multiplications.  You can say the your algorithm is,
say, O(n) in terms of matrix multiplications, even though each one of
those might be O(m^3) where m is some measure of the size of the matrix.
The algorithm won't be O(n) in run-time but you've been able to
characterise an important aspect of it -- home many multiplies it does.

There's another detail that's often ignored.  The algorithm above is
also O(n log(n)), and it's O(n^2) as well!  "Big O" means, roughly, "no
worse than".  There are other symbols (little o and big theta for
example) that have narrower meanings, but they are not much used when
talking casually.

<snip>
-- 
Ben.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web