Results 1 to 2 of 2

Math Help - What is the Computional Complexity of this ?

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    1

    What is the Computional Complexity of this ?

    I'm new to this forum so first i want to say warm "Hello" to everyone, and especially to those that will help me (if any)

    I have nothing special or very complicated here, i just need to know what will be the computational complexity of the simple algorithm below.

    I am almost certain it should be O(N^2), but I just need to make sure.

    Code:
    int SomeFunction( int VarX ){
        
        int Result = 0;
        int Count = 0;
    
        for (int i = 0; i < VarX; i++){
            for (int j = 0; j <= 0.7 * VarX; j++){
                Result = i + log(j*j);
                Count++;
            }
        }
    
        return 0.3 * Result;
    }
    Last edited by ShadowPhantom; January 23rd 2009 at 11:30 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by ShadowPhantom View Post
    I'm new to this forum so first i want to say warm "Hello" to everyone, and especially to those that will help me (if any)

    I have nothing special or very complicated here, i just need to know what will be the computational complexity of the simple algorithm below.

    I am almost certain it should be O(N^2), but I just need to make sure.

    Code:
    int SomeFunction( int VarX ){
        
        int Result = 0;
        int Count = 0;
    
        for (int i = 0; i < VarX; i++){
            for (int j = 0; j <= 0.7 * VarX; j++){
                Result = i + log(j*j);
                Count++;
            }
        }
    
        return 0.3 * Result;
    }
    Yes, the computational complexity is on the order of N^2, if N is the argument of the function (which is called "VarX" in your code).

    I guess you erased a few lines of your program before posting it, because otherwise it looks pretty strange: the "Result" is computed lots of times, but used only at the end, and the "Count" remains unused.

    By the way, here's a tip to improve (a very little bit) the complexity: in your code, the product 0.7 * VarX will be computed a lot of times. You should for instance let Y=0.7 * VarX before the loops, and compare "j <= Y" instead of "j <= 0.7 * VarX". In this case, this won't substancially change the speed, but it may be significant sometimes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 06:55 AM
  3. Computational Complexity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2010, 07:48 PM
  4. Computional Methods Problem with Fortran programming
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 15th 2009, 05:22 PM
  5. Complexity theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 14th 2006, 06:47 AM

Search Tags


/mathhelpforum @mathhelpforum