2
votes
2answers
75 views

Solving the equation $n\log n = 10^9$

This seems very basic (I guess my calculus needs brushing up). Is there a way to find n without a calculator in this one? $10^{9} = n\log(n)$ My Attempt (log is base 2 base on the book convention.) ...
1
vote
1answer
124 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
29 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
120 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
180 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
1k 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
218 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
118 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 ...