Linked Questions

5
votes
1answer
4k views

Do not understand why log n = O(n^c) (for any c>0) [duplicate]

Can anyone help me understand this equation? $\log (n) = O(n^c)$ (for any $c>0$) Does it mean that $O(\log (n)) < O(n^c)$ (for any $c>0$)? Added: Please also prove that $\log (n) = O(...
5
votes
1answer
35k views

Big-O complexity of sqrt(n) [duplicate]

I'm trying to backfill missing CS knowledge and going through the MIT 6.006 course. It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather ...
1
vote
1answer
11k views

How to rank these functions in increasing order of complexity [Algorithms]? [duplicate]

I have the following functions: What is the correct order of these functions in increasing complexity? I could always start entering values in these functions and check the corresponding output to ...
-2
votes
1answer
4k views

Does ln n ∈ Θ(log2 n)? [duplicate]

Is that statement false or true? I believe it's false because ln(n) = log base e of n. So therefore, log base 2 of n can be a minimum because in 2^x = n, x will always be less than y in e^y = n. ...
1
vote
2answers
2k views

What is the Big Theta of $(\log n)^2-9\log n+7$? [duplicate]

How can I find the Big Theta of $(\log n)^2-9\log n+7$? I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
0
votes
2answers
1k views

Show that $x^3 = O(x^4)$ and $x^4 \neq O(x^3)$ [duplicate]

Show that $x^{3}$ = $O(x^{4})$ but that $x^{4}$ $\neq$ $O(x^{3})$.
-2
votes
1answer
2k views

What is the Big O of $2^{\log \log n}$? [duplicate]

What is the Big O class of the following expression: $$2^{\log \log n}$$ I think the Big O is $2^n$ as I assume $\log \log n$ to be $n$. Is my assumption correct?
0
votes
2answers
662 views

asymptotic growth of n^log log n [duplicate]

I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ ...
-2
votes
3answers
1k views

Big O relationship between $n^{10\log n}$ and $(\log n)^n$ [duplicate]

I need help with a home task with computer science. the problem is: compare the two complexity functions: $F(n) = n^{10\log n}$ and $G(n) = (\log n)^n$. Which is $O(\ )$ of the other? Which is $\Omega(...
1
vote
1answer
831 views

Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
0
votes
1answer
1k views

Big O Asymptotic complexity [duplicate]

I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise. The answer I ...
0
votes
1answer
169 views

Which one grows faster asymptotically: $\log(\log^an)$ or $\log^a(\log n)$ [duplicate]

Could someone explain to me which function grows faster? $f(n)=\log(\log^an)$ or $g(n)=\log^a(\log n)$
2
votes
1answer
482 views

Show that 6n^2 + 12n is O(n^2) [duplicate]

I understand how I would do this if the problem were as such $8n + 5$ is $O(n)$ $c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$ we ...
0
votes
1answer
175 views

Understanding Big O [duplicate]

I'm just trying to get my understanding of big O down. I know the concept and the basics but I'm a bit confused about what it means to be equal to big O of something. For example, is $2^{2n} = O(2^{...
3
votes
2answers
113 views

Which of $e^n$ and $2n^2$ grows faster? [duplicate]

How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.

15 30 50 per page