O Notation Help

Question

I am getting stuck with the class work we got this week and its a subject i really want to learn so for once i thought i would do the additional reading!!!!

The method is provided for us and i am just writign some test cases. This is where my knowledge gets a little hazy. If the time increases then i am underestimatign the complexity i believe? in this case n^3 isnt enough and n^4 is too much, hence the gradual reduction to 0.

That means there is a compelxity that lies between the 2, and this is where log n comes in as log n is a value less than n? but this is as far as my knowledge goes

i was really hoping someone could clear this confusion up for me with a better explanation than whats on the lecture slides as they make no sence to me at all, thanks

/**
 * Number 5
 */
public int Five(int n)
{
    int sum=0; 
    for(int i=0; i<n; i++){
        for(int j=0; j<i*i; j++){
            sum++;
        }
    }

    return sum;
}

---

   public void runFive()
    {
// Test n^2 complexity 
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN2(Five(5), 5) + " This is to test the value of 5 in a n^2 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN2(Five(10), 10) + "This is to test the value of 10 in a n^2 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN2(Five(100), 100) + "This is to test the value of 100 in a n^2 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN2(Five(1000), 1000) + "This is to test the value of 1000 in a n^2 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN2(Five(10000), 10000) + "This is to test the value of 10000 in a n^2 test" );

// Test n^3 complexity          
//         System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN3(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
//         System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN3(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
//         System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN3(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
//         System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN3(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
//         System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN3(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );
//         

//Test n^4 complexity
        System.out.println("We are passing the value 5, This returns us an n value of " + Five(5) + " , With a time complexity of " + complexityN4(Five(5), 5) + " This is to test the value of 5 in a n^3 test" );
        System.out.println("We are passing the value 10, This returns us an n value of " + Five(10) + " , With a time complexity of " + complexityN4(Five(10), 10) + "This is to test the value of 10 in a n^3 test" );
        System.out.println("We are passing the value 100, This returns us an n value of " + Five(100) + " , With a time complexity of " + complexityN4(Five(100), 100) + "This is to test the value of 100 in a n^3 test" );
        System.out.println("We are passing the value 1000, This returns us an n value of " + Five(1000) + " , With a time complexity of " + complexityN4(Five(1000), 1000) + "This is to test the value of 1000 in a n^3 test" );
        System.out.println("We are passing the value 10000, This returns us an n value of " + Five(10000) + " , With a time complexity of " + complexityN4(Five(10000), 10000) + "This is to test the value of 10000 in a n^3 test" );

    }

---

Here are the complexity Methods

public double complexityN2(double time, double n)
{
    return time / (n * n);
}

public double complexityN3(double time, double n)
{
    return time / (n * n * n);
}

 public double complexityN4(double time, double n)
{
    return time / (n * n * n * n);
}

public double complexityLog(double time, double n)
{
    return time / (Math.log(n) * (n*n));
}

Answer 1

The only question-mark in your question appears at the end of this sentence:

That means there is a compelxity that lies between the 2, and this is where log n comes in as log n is a value less than n?

That sentence is not a question, it is a statement: what are you asking here?

If you are asking what log(n) is, then it is the number p which, when 10 (denoted log₁₀) or e (when talking about the natural logarithm) is raised to that power (i.e. 10^p, e^p) yields n. Hence it goes up very slowly as n increases (it is the exact opposite of an exponential increase in fact):

log₁₀(10) is 1 (10¹ == 10)
log₁₀(100) is 2 (10² == 100)
log₁₀(1000) is 3 (10³ == 1000)

Apologies if you already knew all this.

Answer 2

Keep in mind that big-O notation describes the behavior as the number of items approaches infinity. As such, you shouldn't expect to see an exact fit when dealing with almost any practical amount of computation. In fact, you don't necessarily see an exact fit under any circumstances -- it may approach a fit asymptotically, but even when (from a practical viewpoint) the number involved is really large, it's still not a very close fit. For as small of numbers as you're using for part of your test (e.g., 5, 10, 100) the fit will often be extremely poor even at best.

From a viewpoint of timing, most implementations of Java make life substantially more difficult as well. The problem is that most JVMs will interpret the first few (where "few" is rather loosely defined) iterations of some code, before they decide it's being executed often enough to be worth compiling to more optimized machine code. The numbers you're using are almost certainly small enough that in some cases you're timing interpreted code and in others compiled code (and somewhere in there, getting an execution that includes the time taken to compile the code as well). This has no real effect on the accuracy of big-O notation, but (especially for small number) can and will have a substantial effect on how closely your timing comes to fitting what big-O would predict.

Answer 3

in this case n^3 isnt enough

That's not true. The outer loop in Five runs exactly n times. For each value of i, the inner loop runs exactly i² times, so the number of steps the outer loop does is the sum of i² while i runs from 0 to n-1, which is n/6 - n²/2 + n³/3 (simple to prove with induction). This is a polynomial of third degree, therefore it is O(n³).

Answer 4

Try to understand it like this- We need to find the number of times the loops will execute to find the time complexity. The sum here also represents the same number, that is why you can use it in place of time in your complexity functions. This assumption is based on the assumption that each processing of a statement takes a constant time. If we count the number of times the loops run- for i = 0 the inner loop runs 0 times for i = 1 the inner loop runs 1 time for i = 2 the inner loop runs 4 times for i = 3 the inner loop runs 9 times so for i = m the inner loop runs m*m times

So the total number of statements processed can be found as -- sum = 0 + 1 + 4 + 9 + .... + m*m + ... +(n-1)(n-1) sum = 1 + 4 + 9 + .... + mm + ... +(n-1)*(n-1) These are squares of natural numbers sum of first N natural numbers can be found as - N(N+1)(2N+1) / 6 in our case N=n-1 so sum = (n-1)(n)(2n-1) / 6 sum = (n.n -n) (2n -1) /6 sum = (2n.n.n - 2n.n - n.n -n) /6 sum = (2n^3 -3n^2 -n) / 6 sum = 1/3n^3 - 1/2n^2 -1/6n

Now, the Big O will only consider the highest order of n.. So your complexity is of the order of n^3

Now your time complexity function for n^3 will take exactly this number and divide it by n^3 so your sum would be like 1/3 - 1/2n^-1 -1/6n^-2.

and for n^4 , an even smaller number, which will get even smaller as n increases which explains gradual reduction to 0.