# Tagged Questions

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)$ ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9424025416374207, "perplexity_flag": "middle"}