Tagged Questions
1
vote
1answer
47 views
Difficulty proving / disproving the following equalities relations ( Big Ω)
I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations.
Here are the three relations:
$ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $
...
1
vote
0answers
22 views
Evaluating a simple sum bound
I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution.
I would like to advise with you if this is the right way because It is really getting more complicated than It ...
0
votes
1answer
63 views
Prove that the little-o definition doesn't hold for two function (f and g)
I need your help with the following statement:
Show there exist two function $f(n), g(n)$ such that meet the following definition:
$g(n) = O(f(n))$ and $f(n) \ne O(g(n))$
But don't meet the ...
0
votes
2answers
83 views
Some Big-O complexity definition proofs
I'm trying to prove (by definition) the following but to no avail:
$n^{n/2} \ne O(3^{n/2}) $
$n! \ne O(3^n)$
$(n-b)^a = \Theta(n^a)$
$a,b $ are both constants whereas $a > 0 $ and $b$ ...
0
votes
2answers
170 views
Little-o proof by definition
I'm trying to figure out how to prove the following but to no avail.
Given the following functions :
$f(n) = n^3 -4n$
$g(n) = 5n^2 + 3n$
I have to show that $g(n) = o(f(n))$
by definition, that ...
1
vote
3answers
89 views
Order of magnitudes comparasions
I have a list of order of magnitudes I want to compare.
My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation.
I need your help with the following.
I ...
1
vote
1answer
113 views
How to continue this argument/proof?
I was wondering to myself what the actual run time of Mergesort was, so I thought like this:
We have the sort operation that takes time $s(2) = 1$ and $s(1) = 0$. Merging two sorted sequences with ...
