Explain O(n) notation

This is a discussion on Explain O(n) notation within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Surprisingly in the many math courses I've been forced to take for my cs degree I haven't come accross O(n). ...

  1. #1
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704

    Explain O(n) notation

    Surprisingly in the many math courses I've been forced to take for my cs degree I haven't come accross O(n). At least not that I remember, perhaps it's the context thats throwing me off.

    Any one feel like explaining it?
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    When you hear "O" you can pretty much substitute uppebound disregarding constant factor. For instance, you can say an algorithm is O(n^2) and you know that a function for the time(t) and some nonnegative constant c 0 < f(t) <= c * n^2.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    One restriction that I forgot to mention is that it's possible to restrict the use of n so that n is greater than n_0. This way a function can behave like n^3 for n < 10 but if for n > 10 it behaves like n^2 the bound is O(n^2)(it is still also n^3).

  4. #4
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544

  5. #5
    mov.w #$1337,D0 Jeremy G's Avatar
    Join Date
    Nov 2001
    Posts
    704
    Lame, some on actually gave me negative reputation for this thread. Some people are simply jackasses.
    c++->visualc++->directx->opengl->c++;
    (it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 07:44 AM
  2. CamelCase VS Hungarian notation, which is better?
    By meili100 in forum C++ Programming
    Replies: 4
    Last Post: 04-22-2007, 10:31 PM
  3. I need help with RPN notation!!!
    By schnoor22 in forum C++ Programming
    Replies: 2
    Last Post: 04-09-2007, 06:12 PM
  4. polish notation calc problem
    By deedlit in forum C Programming
    Replies: 6
    Last Post: 06-14-2004, 11:17 PM
  5. Can someone explain "extern" to me?
    By valar_king in forum C++ Programming
    Replies: 3
    Last Post: 09-16-2001, 01:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21