O(2^n) and O(n!) complexity?

This is a discussion on O(2^n) and O(n!) complexity? within the C Programming forums, part of the General Programming Boards category; I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know ...

  1. #1
    Registered User
    Join Date
    Mar 2013
    Posts
    24

    O(2^n) and O(n!) complexity?

    I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know most of the time recursion takes exponential time but is there any other example can someone give me, also the O(n!) complexity.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Notice that these two complexities are generally bad for "an everyday" algorithm and if you come up with an algorithm that has this much time complexity, then you must think twice!

    The O(2^n) case.
    Assume you want to find all the arrangements of set of n elements! How many are there? 2^n.
    So, in order to find them, you need an algorithm of O(2^n) complexity (time).

    As for the other case, I do not have anything in mind...
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Well, after googling, go here. In that table you can find some examples
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Actually, I think that every recursive algorithm of the form: Τ(n)=nT(n-1), results in O(n!)
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,340
    An obvious example of O(n!), is any algorithm that produces all permutations of n elements since it generates n! permutations. Wiki description of an example algorithm:

    permutations_in_lexicographic_order.htm

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by dotnet13 View Post
    I'm familiar with most of the algorithm time complexity, but not fully sure about exponential and factorial complexity, I know most of the time recursion takes exponential time but is there any other example can someone give me, also the O(n!) complexity.
    The travelling salesman problem is N!. The salesman has to do a tour of N cities, visiting each one only once. So the number of orders is N! (start at a random city, so N choices, visit a random next one, so N-1 chocies, and so on. It's O(N!) rather than N! exactly because a reverse tour is exactly the same distance and, usually, the tour is specified to start and end at the same city.

    A simple protein model might treat all residues as either hydrophilic or hydrophobic, and calculate their shapes. (Some people think that evolution started like this, with the RNA code just specifying either "Hydrophobic" or "hydrophilic" amino acids, to create globs of approximately consistent shape). So if we want to calculate a library of N-mers, we need 2^N examples.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Malcolm, please check what you say before you say it. Moreover, it would be wise to read the whole thread (it is not that big...) before posting, because you could find what you should check!!!

    The travelling salesman problem has complexity O(N!), when it is to be solved via brute force........... Check the link above for more information
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Cyclomatic complexity
    By Sony26 in forum C Programming
    Replies: 9
    Last Post: 04-01-2012, 11:03 PM
  2. Complexity
    By spikestar in forum C Programming
    Replies: 9
    Last Post: 02-09-2010, 05:11 PM
  3. complexity
    By ibrahim630 in forum C Programming
    Replies: 7
    Last Post: 06-04-2009, 11:42 AM
  4. Complexity
    By mMarko in forum C Programming
    Replies: 7
    Last Post: 01-07-2009, 04:51 AM
  5. Algorithm - Complexity.
    By visitant... in forum C Programming
    Replies: 5
    Last Post: 05-13-2003, 03:24 AM

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