Question

Let k be a natural number constant. Suppose you have two algorithms that solve the same problem with running times f(n) = k*n^k and g(n) = 2^n

Answer 1

prove \[f \in O(g)\]

Answer 2

I'm thinking how to formally state this or write it but basically the classes f(n) are all polynomial and the classes g(n) are exponential in time. So you can do any polynomial time algorithm in exponential time. So all polynomial time algorithms are contained in the set of all exponential time algorithms If you think of it in terms of complexity classes...

Answer 3

So I suppose we just choose a particular n in g(n) to make it equal to k n^k
let's see:

Answer 4

Hmm...

Answer 5

O(f) = O(n^k) and O(g) = O(2^n)
So let's go to the definition

Answer 6

http://prntscr.com/4sl67q

Answer 7

Need to get rid of the dependence on the instance size n
and find a constant M that works... it can depend on k

Answer 8

just thinking... been a while since I've had to be this exact with big O notation

Answer 9

Its sorta new to me. I'm gonna post the definition I have then my thoughts? I think I might have an idea.

Answer 10

Just thinking we can use this:
----> http://prntscr.com/4sl6qm

Answer 11

So fiddling around with how to get M from the set of inequalities I presented it probably doable, but not intuitive at least to me. Better yet, just use this idea ^

Answer 12

So if you can solve that the limit superior is finite of f(n)/g(n) you've effectively shown that f(n) is contained in the order of g(n) as large enough instances g(n) out grow large instances of f(n)

Answer 13

The limit superior as just the limit of the supremum... it's just a way to cut off small values of n that might be problematic and different from the long term trend in the complexities

for example if you have k = 5 then 5 n ^ 5 is larger run time than 2^n for small values of n

Answer 14

So... http://prntscr.com/4sl76g

Answer 15

intuitively it's definitely 0 ^

Answer 16

http://prntscr.com/4sl7ah

Answer 17

Hm. Not sure how to make it more precise than that.
Questions?

Answer 18

just trying to digest it all. We were given a different definition/method to prove it, but I see where you're coming from with this

Answer 19

What method?

Answer 20

This is the definition we were given:
f(n) = O(g(n)) means c*g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always less than or equal to c*g(n), for large enough n (i.e. n greater than or equal to n0 for some constant n0)

Answer 21

Then you can use this along with induction to solve, I'm just not entirely sure how for this problem

Answer 22

Induction... hmm

Answer 23

Well, I've never done it here before. But the issue is to induct on n or k. So I think we induct on k. Meaning we start with a particular k value.

Answer 24

Show that the complexity result f = O(g) holds then assume is holds up to an arbtirary k value and then show it must hold then for k+1

Answer 25

here's a similar example I found http://stackoverflow.com/questions/11446029/using-big-o-to-prove-n2-is-o2n

Answer 26

http://prntscr.com/4sl97e

Answer 27

I don't like that start^ - thinking on it...

Answer 28

n^2 and 2^n don't have the same problems because of the k, it's easy to make the induction start

Answer 29

Ah, so it's still an issue with the inductive proof how to choose the constant C
or the n0. I think that's much more troublesome, not saying impossible.

Answer 30

Ya that's kindof the way he suggested to do it, and while the limit proof makes sense, I figure I should probably try to figure this method out as well.

Answer 31

It would be easy to solve if it weren't for the k, I think. With the unspecified constant, I feel like you have to make too many assumptions since you don't know what it is. The way I attempted to go about it was to set c=k and try something from there

Answer 32

http://prntscr.com/4slapr

Answer 33

Yes, so just came up with this out of the blue
M(k) is fine...dependence of M on k
So supposing M(k) = k^(k+1) and for instances such that n >= k

Answer 34

http://prntscr.com/4slayq

Answer 35

then we need to show that the inequality holds, just thinking on paper...

Answer 36

http://prntscr.com/4slbwq

Answer 37

We can then try an inductive proof on this: ^

Answer 38

---> http://prntscr.com/4slcvz

Answer 39

this gets somewhere, ^ just need to revise the choice a bit
the choice of M

Answer 40

http://prntscr.com/4sldhx

Answer 41

So I made the choice that M = k^(k+1)
I want to show that for all instances where n >= k then that n^k < k^k * 2^n
So for n = k, the induction start, it's clear. k^k < k^k * 2^k since 2^k > 1
so k > 1. Now we assume this proposition holds for the all n0 > n > k
And I want to show it holds true in the n0+1 case
So I start with the inequality but in the n0+1 case, that is:
Well, I start with the expression (n0+1)^k
and eventually I want to show that < k^k * 2^(n0+1) essentially a doubling

In order to do that I've used the binomial theorem to expand (n0+1)^k
but the estimates it's giving me are not the best at the moment
clearly... (k choose l) is < k^k all the time and then we have k+1 terms in the series
so (k+1) * k^k * n0^k where n0^l < n0^k clearly
and then we can use the induction hypothesis, but that estimate is not tight enough to give us just the doubling

Answer 42

There have to be tighter estimates on the binomial coefficient
Google time!

Answer 43

----> http://prntscr.com/4slf9e
Actually, that's the original estimate nearly isn't it

Answer 44

I will work on this independently... so it's not so much of a time suck
Sorry about that, If nothing else limit superior

Answer 45

I completely understand. Thanks for all the help, though. I think I can get a good majority of it between the limits and induction we've done. I wish I could give more then 1 medal for taking up so much time :(

Answer 46

No, that's fine. To me, medals have no value at all. Words, and that's it. ;)
I appreciate that you want to go on the journey to find the answer with me, rather than expect me to always be a robot knowing the answers immediately.
Good luck with this, I do have to go now.

Whee.

Answer 47

Okay. Thank you again for all your help

Answer 48

My pleasure.