Questions tagged [landau-notation]

Questions about asymptotic notations such as Big-O, Omega, etc.

Filter by
Sorted by
Tagged with
4 votes
2 answers
47 views

Finding the constants in Landau notation

I am trying to find the constants $n_0$ and $c$ to show that some given functions belong to the $O(\cdot)$ equivalence class. But, while it seems easy, I am not sure whether I am allowed to do what I ...
user avatar
  • 173
2 votes
1 answer
56 views

Trying to understand the basic about recurrence trees

I have little background on recurrence trees, and I am working on the following exercise: Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
user avatar
  • 187
3 votes
2 answers
67 views

Linearity property of summation applied to Big Theta notation (CLRS math background appendix)

Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation: $$ \sum_{k=1}^{...
user avatar
3 votes
1 answer
169 views

Shifted Big Os. How to say O((n+c)!) = O(n!)?

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is $nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$ Strictly, there is no constant factor that would make ...
user avatar
  • 133
1 vote
2 answers
56 views

Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$

I am trying to proof $f\in o(g)$ Let be $r,p\in \mathbb{R}$ with $p>0$ We have $f(n)=ln^r (n)$ and $g(n)=n^p$ I have already proofed that $ln(n)\in o(n)$ via l'Hospital $\lim\limits_{n\to \infty}\...
user avatar
1 vote
1 answer
38 views

Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence. Definitions: Let f,g be functions. $f(n)\in \mathcal{O}(...
user avatar
1 vote
2 answers
45 views

Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

I have encountered the following question in my homework assignment in Data Structures course: "Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?" ...
user avatar
  • 13
1 vote
1 answer
79 views

Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$? How can the function on the left be compared to a whole set?...
user avatar
  • 135
1 vote
1 answer
67 views

Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$

Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$ Can I keep the same constant $c$ in each of the cases? Consider two cases: $$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c⋅...
user avatar
0 votes
2 answers
80 views

How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

I am trying to answer this question: $3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$ My question is how to solve this question. Here is what I have tried so far: I applied the definition $3x^3 + 2x + 1 ...
user avatar
1 vote
3 answers
142 views

Prove little o with just the definition

I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation. Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am ...
user avatar
  • 11
0 votes
0 answers
18 views

O nation prove with limit theroem? [duplicate]

I'm working on my school homework,even though i found all three of these. It says use limit to compare. I confused , what should i do, i mean its obvious C A B
user avatar
0 votes
1 answer
60 views

Big O Tires Question? [duplicate]

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.) What's the runtime of this code? ...
user avatar
  • 141
0 votes
1 answer
90 views

How to tackle Big O proofs that involve multiple parameters

I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am ...
user avatar
  • 15
0 votes
1 answer
120 views

Asymptotic growth of a function containing a sum

How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
user avatar
0 votes
2 answers
75 views

Is this a correct way to thing about asymptotic notations?

I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering ...
user avatar
2 votes
2 answers
604 views

Induction proofs in Big-O notation

I'm not sure how go about this question: Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
user avatar
1 vote
1 answer
86 views

How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
user avatar
  • 113
14 votes
3 answers
3k views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
user avatar
1 vote
2 answers
575 views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$ \sum_{k=1}^{n-1} O(n). $$
user avatar
2 votes
1 answer
75 views

When are log complexities considered equivalent?

Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$? Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.
user avatar
  • 21
4 votes
2 answers
255 views

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following: $$ \sum_{i=1}^n O(i) $$ is not the same as (I'm not using DNE because the book explicitly ...
user avatar
1 vote
1 answer
47 views

Substitution for Landau's O notation formula

I found the following description when I was reading a paper on computational complexity theory. This can be done ... in time 2n・poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n・poly(n). I ...
user avatar
  • 59
0 votes
0 answers
54 views

which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]

i am learning this post about Big O, which gives this formula $$\log n = O(n^{0.000001})$$ why is that?
user avatar
  • 576
0 votes
0 answers
20 views

Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
user avatar
  • 115
0 votes
3 answers
246 views

How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
user avatar
0 votes
3 answers
100 views

If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?
user avatar
2 votes
1 answer
538 views

Proving Big Omega of a polynomial without limits

Here is the definition of $\Omega$: $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$. Here is one theorem: If $f(n) = a_m n^m + \...
user avatar
  • 23
2 votes
2 answers
59 views

What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$. However, I went through the following ...
user avatar
  • 285
1 vote
1 answer
90 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
user avatar
  • 19
1 vote
1 answer
53 views

Are the following Big Oh Notations equivalent?

In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent. $\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$ $\...
user avatar
48 votes
10 answers
11k views

O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
user avatar
  • 591
0 votes
1 answer
9k views

How come O(n) + O(logn) = O(logn)

How come O(n) + O(logn) = O(logn)? When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
user avatar
0 votes
1 answer
58 views

Is this a valid use of big-O notation?

Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results. ...
user avatar
1 vote
1 answer
982 views

Introductory explanation of the Big-Oh properties

I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
user avatar
1 vote
2 answers
112 views

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ? Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
user avatar
1 vote
1 answer
34 views

Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$. I came up with following proof but i dont know it's correct or not. $$g = O(f)$$ $$g \le c_1*f $$ $$h \le c_2*f $$ ...
user avatar
1 vote
1 answer
146 views

Asymptotic Notation Analysis

2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1 since 2^n may or not be element of O(3^n) I need a hint to figure the problem
user avatar
0 votes
1 answer
362 views

complexity class of functions [duplicate]

What would these statements mean if f(n) and g(n) are functions over natural numbers? g(n) is in Θ(f(n)). and An algorithm is in the complexity class Θ(f(n)).
user avatar
1 vote
3 answers
633 views

What is the constant $C$ in the definition of asymptotic notations?

For example in the definition of $\Theta$: $f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for ...
user avatar
  • 151
0 votes
1 answer
31 views

How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?

given: $$m_1+m_2+...+m_k=m$$ How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$? I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but ...
user avatar
2 votes
1 answer
54 views

Complexity Reduction Analysis

I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...
user avatar
0 votes
2 answers
234 views

Two questions about complexity class

Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower? What is the name of the ...
user avatar
  • 261
3 votes
1 answer
46 views

Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel ...
user avatar
  • 133
0 votes
0 answers
151 views

If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
user avatar
0 votes
1 answer
561 views

Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
user avatar
1 vote
0 answers
58 views

Can there be functions in o(1) in algorithm analysis?

I saw a similar question to this one here but it's not quite the same as mine: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? I've just started a course in data structures and ...
user avatar
-1 votes
1 answer
86 views

Algorithms - In which relation to the big O notation are the functions lg n and ln n? [duplicate]

I want to prove in which relation the two functions stand to each other with the help of a proof. But how?
user avatar
  • 1
6 votes
1 answer
812 views

What does the "big O complexity" of a function mean?

What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
user avatar
6 votes
3 answers
1k views

How did they cancel out O-terms in this fraction?

While reading a book about algorithms, I came across this derivation: $$ \frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} = \frac{2\ln(2N) + O(1)}{\ln N+O(1)} = 2 + O\left(\frac{1}{\log N}\right). $$ ...
user avatar

1
2 3 4 5 6