# Tag Info

Is what I wrote about big-O correct? Yes. How do big-Theta sets relate to each other, if they relate at all? They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$. Why do they relate to each other the way they do? The explanation is probably ...
I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect. Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations. However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2)... 18 We have $$\frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.$$ Using Stirling's approximation we can get more refined asymptotics, but we ... 13 You are always free to not use this notation at all. That is, you can determine a function$f(n)$as precisely as possible, and then try to improve on that. For example, you might have a sorting algorithm that makes$f(n)$comparisons, so you could try to come up with another sorting algorithm that only does$g(n)$comparisons. Of course, all kinds of ... 7 "On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g.,$10n \in O(n)$, despite$10n$being 10 times as larger as$n$). They can hardly be considered the same things. What the lecturer is trying to ... 7 While the accepted answer is quite good, it still doesn't touch at the real reason why$O(n) = O(2n)$. Big-O Notation describes scalability At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to ... 6 If the$O$-complexity given is true, then$f(x)\leq c_2n\log n$will not always be true. So in this case, how is$\Theta$-complexity different from$O$-complexity? Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics. There is no such thing as "$\Theta$-complexity" or "$O$-... 6 You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants. Consider the following example:$f_i(n) = i\cdot n$for all integers$i$and$n$. Then, for any integer$i$,$f_i(n) \in O(n)$. If you are not careful, you could end up writing something like: $$\sum_{i=1}^n ... 5 You can write O(f) for any function f and it makes perfect sense. As per the definition, g(n)=O(f(n)) if there is some constant c such that g(n)\leq c\,f(n) for all large enough n. Nothing in that definition says that f must be some sort of "nice" function. But, as other answers have pointed out, g(n)=O(f(n)) and g(n)=O(2f(n)) ... 5 From this post, you can approximate \log(1+x) with x for little values of x. Hence,$$ f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1 $$Therefore, you can't find any constant c, such that f(n) = O(n^c), as it is \Theta(2^n). 5 Your expression is$$ E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$where c is some constant. The simple upper bound for E is$$ E\le c n^2$$which implies that \mathcal{O}(n^2). For a better bound$$E = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 } $$Now it is an easy verification that E is \mathcal{O}(\frac{n^... 4 It may be helpful to understand that Big-O describes a set of functions. That is O(f(n)) = \lbrace g(n) | \exists n,c>0: \forall m > n: c\times g(m) \le f(m)\rbrace The usage of = is kind of unfortunate and using \in would make that relationship a lot clearer. but the set notation symbols are a bit difficult to type so now we are stuck with the ... 4 Look at the definition of O(f(n)), and you see that for example O(2n^2) and O(n^2) are exactly the same. Changing an algorithm from 5n^2 to 3n^2 operations is a 40 percent improvement. Changing from O(5n^2) to O(3n^2) isn’t actually any change, they are the same. Again, read the definition of O(f(n)). 4 How to calculate Big O of T(n) = aT(n^b) + f(n) with 0<b<1? The powerful technique you are searching for is variable substitution. Let S(m)=T(2^m). Then$$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$where g(m)=f(2^m). Now that we have a recurrence relation about S(m), to which we might be able to apply the master's theorem. Here are ... 4 It runs in time O(n). Remember that a function only returns once. In each call to f, the for loop is immediately terminated at i=0 by the return statement, so the function body is equivalent to if n < 100000 return 0; else return f(n-1); However, your answer of O((n!)^2) is not wrong: (n!)^2 is a huge overestimate of the running time,... 4 The worst-case running time of quicksort is \Theta(n^2), and therefore quicksort always runs in O(n^2), and this bound is tight (that is, best possible). The average-case running time of quicksort is \Theta(n\log n). The best-case running time of quicksort is also \Theta(n\log n), and therefore quicksort always runs in time \Omega(n\log n), and ... 4 An obvious function is$$ f(n) = \begin{cases} n \log n & \text{if$n$is even}, \\ 0 & \text{if$n$is odd}. \end{cases} $$It's in O (n \log n), it's not in o (n \log n) and not in \Theta(n \log n). By the way: Every function in \Theta(f(n))) is in O(f(n)), just take the larger constant from the \Theta definition. And every function ... 4 Here are the functions.$$f(n) = \frac{\log(n)}{\log\log(n)}h(n)=\frac n{f(n)}=\frac{n\log\log(n)}{\log(n)}g(n)=f(h(n))=\frac{\log(\frac{n\log\log(n)}{\log(n)})} {\log\log(\frac{n\log\log(n)}{\log(n)})}$$Is g(n) < f(n) in fact true (starting from some n)? Yes, here is a proof. Let us compute the derivative of f(x) with ... 4 The complexity is O(n^2). The reason is that the two inner loops take O(n) time. The first iteration takes i operations, then i/2, then i/4 until it's 0. So we need to compute the sum of i+i/2+i/4+...+1 operations which its upper bounded to 2i. Finally because your outer loop is clearly O(n) the total complexity is O(n^2). 3 an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous ... 3 First, |V| is the number of vertices and |E| is the number of edges. The point is that if a graph is connected it must have at least |V|-1 edges. Therefore, |V|\leq |E|+1, so$$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$Writing |V|=O(|E|) is something of an abuse of notation. O(\cdot) is an asymptotic statement about ... 3 The formula is wrong. The notation f = O(g) is asymmetric, and has the meaning f \in O(g). For more, check our reference question on Landau notation. Other relevant reference questions are this one and this one. 3 The class O(f(n)) consists of all functions \phi such that for some N,c > 0, we have \phi(n) \leq Cf(n) for all n \geq N. The class 2^{O(f(n))} is simply$$ 2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \}, $$which is essentially what you wrote. A different way of looking at this is that O(f(n)) stands for some function \phi(n) such ... 3 I'd just like to add some to the already posted answer and comments. I'm currently studying CS, and every single time big O notation came up, the lecturer at some point mentioned that they in fact are sets, and that f(n) = O(g(n)) really is just wrong notation used for historical reasons, and \in is what would be correct. In fact, the way we defined ... 3 little-oh proof An equivalent but more straightforward question would be why \lg n is dominated by \lg^2 n, that is why \lg n \in o(\lg^2 n). Then based on the definition of little-oh we need to show that for any choice of constant c > 0 , we can find a constant n_0 such that the inequality \lg n < c \lg^2n holds for all n > n_0 ... 3 In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing t_a(n) as 2^{s_a(n)} and compare s_a(n) with \sqrt{\log_2 n}. Additionally, beware of using a program to check asymptotic comparisons: e.g. f(n)=n^{10^6} and g(n)=(1,0000000000000001)^n 3 Suppose T(n) is the time complexity of the above code. Then:$$T(n) = \sum_{i=0}^{n-1}(i + \frac{i}{2} + \frac{i}{4} + \cdots +‌ 1) = \sum_{i=0}^{n-1}i (1 + \frac{1}{2} + \frac{1}{4} + \cdots +‌ \frac{1}{2^{\log(i)}})$$As we know 1 < 1 + \frac{1}{2} + \frac{1}{4} + \cdots +‌ \frac{1}{2^{\log(i)}} \leq 2:$$\sum_{i=0}^{n-1} i = \frac{(n-1)n}{2} ... 3 The problem is that you are using$n$to mean too many different things without really defining it. You can't say that an algorithm runs in$O(n)$time without specifying what$n$is, unless it is clear from context. In this case it is not clear, and that is what is tripping you up. When we say an integer multiplication algorithm runs in$O(n^2)$time, the ... 3 There is an explicit formula for$\sum_{i=0}^n i^3$, but even without it, you can estimate $$\int_0^n x^3 \, dx \leq \sum_{i=0}^n i^3 \leq \int_1^{n+1} x^3 \, dx.$$ Since$\int x^3 \, dx = x^4/4$, this shows that the sum is very close to$n^4/4$, and in particular is$\Theta(n^4)$. (The explicit formula states that the sum equals$n^2(n+1)^2/4$.) 2 You've almost got it! Remember, you're going to visit each city exactly once in a tour. Which means you have to look up$n-1$distances for each one. This is$O(n)$, since the problem specifies that matrix lookup is assumed to be$O(1)\$.