I would to prove the following example:
n^k = O (c^n) for every k and c>1
It is noticeable that the polynomial function grows faster than exponential function. We try to find k0 > 0 satisfying the condition
fn > = k0 * g(n)
Than
n^k <= k0 * c^n
log(n^k) <= log (k0 * c^n)
log(n^(k/n)) <= log (k0 * c)
k0 >= 1/c*n^(k/n)
So, k0 > 0, positive and small enough, while the value of c is irrelevant... Is it OK?
log(n^k) <= log (k0 * c^n)
k log n <= log k0 + n log c
k log n - n log c <= log k0
log (n^k) - log (c^n) <= log k0
log ((n^k) / (c^n)) <= log k0 | expo
(n^k) / (c^n) <= k0
n^k <= k0 * c^n
=> n^k = O(c^n)
Your step 3 seems wrong, at least I don t see where you got it from. Your conclusion also doesn t seem to prove what was asked for.
For my algorithm analysis course, I ve derived from an algorithm the function f(n) = n^2 - n + 2. Now I need to prove or disprove f(n) ∈ O(n). Obviously it s not, so I ve been trying to disprove that ...
I would to prove the following example: n^k = O (c^n) for every k and c>1 It is noticeable that the polynomial function grows faster than exponential function. We try to find k0 > 0 satisfying ...
I am currently reading an Algorithm s book and came across the Stable Matching Problem. And a question came to mind that I m curious about, but the book doesn t answer. In every SMP is it possible to ...
I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation ...
Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically ...
I m trying to solve problem 50 on Project Euler. Don t give me the answer or solve it for me, just try to answer this specific question. The goal is to find the longest sum of consecutive primes that ...
First of all, is this only possible on algorithms which have no side effects? Secondly, where could I learn about this process, any good books, articles, etc?
I am trying to compare 2 algorithms. I thought I may try and write a proof for them. (My math sucks, so hence the question.) Normally in our math lesson last year we would be given a question like <...