Linked Questions

8
votes
1answer
61k 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 ...
5
votes
1answer
6k 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(...
1
vote
1answer
23k 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
5k 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
4k 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
2k 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
3k 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
2k views

proving big theta [duplicate]

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$ I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as $$10n^3+3n \leq c_1n^3$$ $$0 \leq ...
-2
votes
3answers
2k 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(...
0
votes
2answers
1k 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$ ...
0
votes
1answer
2k 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 ...
2
votes
1answer
1k 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
245 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)$
1
vote
1answer
872 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 ...
1
vote
1answer
1k views

Why is $\log n = O(2^n)$? [duplicate]

In my theoretical computer science book I have the following statement regarding the space complexity of $f(n)=2^n$: $$\log(n) = O(f(n))$$ I can't understand how this is true, any help will be ...

15 30 50 per page
1
2 3 4 5
13