27

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 ...


21

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)$.


Only top voted, non community-wiki answers of a minimum length are eligible