Thread: Complexity

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    9

    Unhappy Complexity

    Hi, I started learning C recently and I don't have much experience. I need to make a program that will factorize an entered integer number and I should also explain the program. No problems with that . However I should also write the complexity of the program (you know like O(n), O(log2n) etc.). I'm stuck there, how should I write the complexity using n (the entered number)? Basicaly it doesn't depend on how big is the entered number, but how big are his factors. Some big number like 3^20 will be factorized faster than some relatively little prime number like 5413. Can I somehow express my program's compexity using n or there is another way I should do that? Any help will be appreciated.

    P.S. yes the program probably can be improved, but that isn't important at the moment (4294967291 is the largest prime that can be stored in unsigned int ...and the program factorizes it for <1s, so I don't think there is any need for faster algorithm :P). Maybe if I used unsigned long long...

    P.P.S. sorry, names and text in the program aren't in English, I'm in a hurry, can't translate right now. But you get the point ...I hope . Sorry for reading all this
    Last edited by mMarko; 01-06-2009 at 05:16 PM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I would suppose basically it is something like O(n) - with a high chance of earlying out.

    If you need to factorize a lot of numbers you might keep an array of primes at hand (Which I think I have used for some Project Euler problems.)

    For factorizing just one number I guess it is fast enough.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
               fakt[faktBr].osnova=2;
               fakt[faktBr].stepen=0;
               while(n%2==0){
                     n/=2;
                     fakt[faktBr].stepen++;
               }
               faktBr++;
    could be made into a function - it is after all repeated twice in your code, and it's complex enough that the overhead of a function call will probably make minimal difference.

    Code:
        for(i=3;i<=sqrt(n);i+=2){
    Are you sure that you can not get more than 9 factors by using a value below 2^32? I'm not sure, that's why I'm asking.

    --
    Mats
    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.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think this means that no factor can be larger than square root of the current value.

    Perhaps as an optimization the sqrt call could be moved elsewhere. E.g if a number is not divisible by 3, 5, 7, etc there's no point in recalculating the square root.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    I think this means that no factor can be larger than square root of the current value.

    Perhaps as an optimization the sqrt call could be moved elsewhere. E.g if a number is not divisible by 3, 5, 7, etc there's no point in recalculating the square root.
    Sorry, I messed up my post - yes, that was what I was meaning to say, but then I changed my mind but didn't remove the code-segment I meant to write the comment on, but after more thinking, I think it is correct to say:
    * take the sqrt of n before the loop.
    * when you find a factor, after the while loop, re-calculate the sqrt(n) variable [as n is now i ^ stepen smaller].

    --
    Mats
    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.

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    9
    Quote Originally Posted by matsp View Post
    Are you sure that you can not get more than 9 factors by using a value below 2^32? I'm not sure, that's why I'm asking.
    Well yes I am . The smallest number with 10 different factors would be 6692786100 (it's factors are the first 10 primes) and that's over 2^32

    Thanks for the other advices too, will try to do it...

    P.S. so it's O(n)? Would you mind explaining how you get that? I hope I'm not bothering you too much .

    I tried a little but... If the input is a prime number then I guess the for loop will repeat (sqrt(n)-1)/2 times, right? But then if it's a composite that doesn't apply. How can I put all cases in one formula ...or should I just look at the worst case?
    Last edited by mMarko; 01-07-2009 at 04:41 AM.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by mMarko
    The smallest number with 10 different factors would be the 6692786100 (it's factors are the first 10 primes) and that's over 2^32
    Actually, the smallest natural number with 10 different natural number factors is 10!, but then you actually mean prime factors

    Consequently, your reasoning is correct, though I note that the number is actually 6469693230.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Jan 2009
    Posts
    9
    Quote Originally Posted by laserlight View Post
    Actually, the smallest natural number with 10 different natural number factors is 10!, but then you actually mean prime factors

    Consequently, your reasoning is correct, though I note that the number is actually 6469693230.
    Well yes we are talking about prime factors, and yes you are right, it's 6469693230, I don't know the number, I calculated it ...don't know if it's my or calculator's fault ...probably mine . Anyway I got the correct number the first time, I guess.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting (asymptotic) complexity problem
    By Petike in forum C++ Programming
    Replies: 8
    Last Post: 01-20-2009, 07:15 AM
  2. Algorithm Complexity
    By logicwonder in forum C Programming
    Replies: 4
    Last Post: 01-09-2006, 06:03 AM
  3. Worst-case complexity of this function?
    By Ariod in forum C Programming
    Replies: 3
    Last Post: 08-17-2005, 02:17 PM
  4. question on time complexity
    By blue_gene in forum C++ Programming
    Replies: 10
    Last Post: 05-16-2004, 05:09 AM
  5. Algorithm - Complexity.
    By visitant... in forum C Programming
    Replies: 5
    Last Post: 05-13-2003, 02:24 AM

Tags for this Thread