Go Down

Topic: Big Oh Problem - Algorithm Efficiency Problem (Read 6222 times) previous topic - next topic

012anonymousxyz

Jul 07, 2013, 06:55 pm Last Edit: Jul 07, 2013, 07:17 pm by 012anonymousxyz Reason: 1
This is a homework problem that I cannot solve.
Basically, list the following in order of increasing rate of growth (such that g(n), f(n)... where f(n) = O(g(n))
a)22n
b)2n2
c)n2log(n)
d)n
e)n2n

My solution:
n, n2log(n) (for obvious reasons)

Next: assume 22n = O(2n2)
22n <= c x 2n2
Let 2n = y
2y <= c x y2
Therefore false (by contradiction -- although I cannot really prove it. But exponentials tend to grow faster than quadratics. Not sure if this is a proper solution)
2n2 = O (22n)
2n2, 22n

next: assume  n2n = O(22n)
Let y = 2n
ny <= c x 2y
No idea about this one because they are both exponentials.

[EDIT]
Ugh, and looking at it now, I cannot substitute y on the right side due to order of operations
22n <= c x 2n2
Let 2n = y
2y <= c x y2
I have no idea how to solve this and really appreciate hints!

[EDIT2]
On the same line as the first edit, I can however do this:
Let 2n = y
22n <= c x n2n
2y <= c x ny
However, once again, although it feels like this would be true, I cannot prove it.

robtillaart


just fill in 1 and 1000 for the n as see what grows  fastest. ( a simple Arduino program can show you the real growth until float explodes ;)

OK, as I noted you did think about it at least for some moments and your intuition is in the right direction I share my solution:
(please imagine the superscripts)

If I am right the order is:    n, n2log(n), 2n2,  22n  n2n

n < n2 < n2log(n)   (linear vs quadratic/polynomal - note the n2 step in between

n2log(n) < n3  < 2n2  (polynomal versus exponential - note the n3 step in between)

2n2 < 22n  as n2 < 2n  (same base so look only at exponent:  quadratic exponent vs exponential exponent)

22n < n2n   as 2 < n (same exponent look only at the base; constant vs linear base)

Please post your sketch to proof the above...
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

012anonymousxyz

#2
Jul 07, 2013, 11:06 pm Last Edit: Jul 07, 2013, 11:25 pm by 012anonymousxyz Reason: 1
Thank you for the reply! Yes, that is the order and I realized that I was going about this all wrong. Since we only have one term monomials with no coefficients, it is impossible to prove using the Big Oh definition. Therefore one must prove by getting the derivative! (or second derivative technically)

I did test though just to make sure. It is in java (please don't hate) as I no longer own an Arduino (classes are over)

Code: [Select]

   public static void main(String[] args){
       int n = 0;
       for(n=0; n<1000; n++){
           float a = (float)(Math.pow(2, Math.pow(2, n)));
           float b = (float)(Math.pow(2, Math.pow(n, 2)));
           float e = (float)(Math.pow(n, Math.pow(2, n)));
           
           System.out.println(a+"\t"+b+"\t"+e);
       }
   }


As expected, e caps out first, then a, then b. Exactly in the order you described.

I appreciate it a lot!

robtillaart

Quote
It is in java (please don't hate)

Why hate a programming language? Some prog languages just fit better or worse to an application (/requirements / constraints/...)
This is a nice fit.

you could copy the output (partially) of the application in a spreadsheet and make a nice graph to see the difference!

PS the main loop only needed to go to 15 :)

Code: [Select]

public class test
{
    public static void main(String[] args)
    {
        int n = 0;
        for(n=0; n<15; n++)
        {
            float a = (float)(Math.pow(2, Math.pow(2, n)));
            float b = (float)(Math.pow(2, Math.pow(n, 2)));
            float e = (float)(Math.pow(n, Math.pow(2, n)));
           
            System.out.println(a+"\t"+b+"\t"+e);
        }
    }
}

(if you have Arduino installed you have an java compiler !)
compile: javac test.java
run: java test
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

012anonymousxyz

#4
Jul 09, 2013, 07:01 am Last Edit: Jul 09, 2013, 03:03 pm by 012anonymousxyz Reason: 1
Hello again! Mr.Rob or if anyone else happens to read this, I have the same question except only two options and they are really tough. I did test to n=1 billion and got an answer, but I am not sure about it.

a)n1/2
b)2(logn)1/2

So there are two things throwing me off: first is the obvious square root on the exponent. The second thing is that the logn is base 10.

Function 'a' maps 1 000 000 000 to 31622
Function 'b' maps 1 000 000 000 to 8.0

The obvious answer is function b = bigOh(functiona)
However, because the second is exponential, I am very iffy. I got a question wrong because I tested to 100,000, but afterward, I realize it took 500, 000 for a certain function to pass different one specifically because... well, see for yourself. Observe the following:

a) 22logn
b) n2.5

I didn't realize that with base 2, 'a' is essentially means 2^n. So at the time, ignoring that fact,
I simply ran a test to 100,000 which returned a bigger value for function 'b' than function 'a'. Function 'a' = BigOh(function 'b')
But for a test that ran to 500,000, function 'a' far surpassed function 'b'. Function 'b' = BigOh(function 'a')
And the reason that function 'a' took so long is because function 'a' has a constant divisor in its exponent because logn is of base 10, which becomes log2n/log210 (constant - log2n

In this thinking, for some value no, 2(logn)1/2 might surpass n1/2

robtillaart

Quote
and got an answer, but I am not sure about it.

not sure about the answer or the implication?

The second one can be rewritten, hint:    log(n) ==> 2log(n)  /  2log(10)
now it is your turn,



Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

westfw

Do you get to use calculus?
"rate of growth" = df(n)/dn
Those equations aren't "nice", but they can certainly be evaluated.

012anonymousxyz

#7
Jul 10, 2013, 09:15 pm Last Edit: Jul 10, 2013, 09:17 pm by 012anonymousxyz Reason: 1
Not sure about the answer.The answer being 2(logn)1/2BigOh(n0.5)
And the calculus was way too complicated for me lol. There were too many lns and the original equation actually remains when you take the derivative of an exponential.

I came up with A solution but I did not factor in the 1/2. I do not know how it would work.
2log10n
=2log2n/log210
=2(log2n)1/log210
=nlog10/log2
=n0.3

I can only imagine with the square root it would be smaller. I got the question right but now I really really want to solve it with the square root factored in.
This is as far as I got:

2rootof(log10n)
=2rootof(log2n)/rootof(log210)
=2rootof(log2n)rootof(1/log210)

I cannot apply any rules further than this.
2rootof(log2n)
cannot be simplified to just n like above

robtillaart

I think you are on the right track as

2^log(n)^1/2  is always smaller than 2^log(n)
==> now if 2^log(n) << n^1/2 than it is solved

2^log(n)  =  2^(log2(n) /log2(10))  =  2^(log2(n)  * 2^1/log2(10))  =  c * n  where c = 2^1/log2(10)) ~1.2320
unfortunately c * n  >> n^1/2    so this way is a dead end .

it would be a lot easier if    2^(logn)^1/2    was   2^log (n^1/2)   ==>  2^log (n^1/2)  == 2^(0.5*log (n)) which would end in c*n again

so can you check the exact formula from b? is it the sqrt(n)  or the sqrt of (log(n))?
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

012anonymousxyz

Sorry for the late reply. And it is (logn)^1/2. That is to say, the sqrt is applied to the n.
So if you can figure out a solution, I'd love to read it. Just maybe not immediately.
The course I'm taking is progressing and I don't even know integrals so I'm swamped atm between work work, 3 courses and the background to keep up with these courses, so sorry for the late reply and I really appreciate all the help you gave!

robtillaart

Quote
so I'm swamped atm between work work, 3 courses and the background to keep up with these courses,

Welcome to the real life ;) as long as you like what you're doing it is fun not work

check this video - http://www.boxofcrayons.biz/free/movies/eightprinciples/ - :)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up