Need help with function..

This is a discussion on Need help with function.. within the C++ Programming forums, part of the General Programming Boards category; Also, the best complexity to detect if something is sorted is O(n). It's a single pass through the list, making ...

  1. #31
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    Also, the best complexity to detect if something is sorted is O(n). It's a single pass through the list, making sure that every element has the correct order in respect to its predecessor. Again, it cannot possibly be faster, because you have to look at each element at least once.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  2. #32
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by master5001 View Post
    What is debateable is what can most rapidly confirm that the data is already sorted. You have the web at your access to my friend. I am not going to search stuff you are capable of looking up on your own. You were given satisfactory explanation to the logic. Even if you have multiple CPU's each reading part of a pile of data, there is always going to be a point where things are only processed on an individual basis. No matter what. I applaud that you are so boldy trying to make something "better."
    Multiprocessing or multithreading will not change the fundamentals of the O(...) method of describing the complexity of an algorithm - it will just [potentially, assuming it's actually possible to parallelise the algorithm] speed up the actual execution, which is still proportional to the number of elements in some way. If it's O(n), then twice as many elements will take twice the amount of time. If you have four processors, it will still take twice as long to do double the number of elements.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #33
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    That was my point. The complexity of the problem is a constant. Thus, there is no suitable way of reducing the absolute best case scenario. Which was my entire point to begin with. I am just not entirely sure where there is any room for cutting corners short of actually not checking every element.

    If you didn't need to have everything sorted, you could theoretically make something with a O(n/x) complexity where x denotes a constant factor in which you skip elements of the data. The objective would simply be to sort data based on probability and skip elements that are in all probability already sorted. However, again, if something is truly randomized the probability of any element being sorted already is low.

    In otherwords, you can make something with less than O(n) complexity if it does a half-assed job of sorting the data.

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM

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