Big Oh Problem - Algorithm Efficiency Problem

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))

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.

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!

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.

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 :wink:

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…

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)

    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)));

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

I appreciate it a lot!

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 :slight_smile:

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)));

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

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.


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

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,

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

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.

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:


I cannot apply any rules further than this.
cannot be simplified to just n like above

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.5log (n)) which would end in cn again

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

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!

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 - - :)