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
38k 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
13k 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
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
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?
-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(...
0
votes
2answers
712 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
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 ...
1
vote
1answer
863 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
185 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
618 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
2answers
591 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 ...
0
votes
1answer
181 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^{...

15 30 50 per page
1 2 3 4 5 12