New answers tagged

3

$O(f(n))$ means: There is a constant c > 0, and an integer $n_0$, so that for every $n > n_0$ the time is less than $c \cdot f(n)$. Note that the integer $n_0$ could be very, very large. And the constant c could be very, very large. If $n ≤ n_0$ then we know nothing whatsoever about the time; the $O(n)$ algorithm could be slower than the $O(n^3)$ ...


0

$O(n)$ is subset of $O(n^3)$ i.e. $O(n) \subset O(n^3)$, which means, that algorithm which have $O(n)$ complexity also have $O(n^3)$. To be sure that one algorithm runs slower, then another, we need it to be in $O(n^3) \setminus O(n)$ or $O(n^3) \cap \Omega(n)$. For explanation let's think about big-$O$ as about inequality - to be less then $n$ always mean ...


1

Let's firstly imagine function $f$: for $k=2$ we have two intervals $(4,5)$ and $(5,6)$ and for $k=3$ we have two intervals $(6,7)$ and $(7,8)$. Accordingly for $f$ we have: $$\quad\quad\quad x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\ f(x)\quad 2^4\quad\quad 2^5\quad\quad\quad 3^6 \quad\quad3^7$$ for ...


1

You have to do three things: Exhibit an algorithm. Prove that it is correct (it outputs the right value). Prove that its running time is $O(|V|)$. @Steven describes one way to prove the running time. One can probably prove correctness using structural induction as well.


2

You can prove that formally by using structural induction. The structure of the proof is as follows: Observe that a preorder traversal of a tree with $1$ vertex requires constant time. Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the ...


0

No comparison based sorting algorithm can be faster than $\theta(n \log n)$. On the other hand, both building the initial tree and removing items and rebalancing take at most log n steps per item.


5

Your analysis of the time complexity is wrong. Specifically this statement: In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at. In fact you can have up to $\binom{n}{s}$ $s$-cliques. You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time ...


2

Big O notation is oblivious to this difference. This is one of its downsides. One reason we use big O notation in the first place is that the exact running time depends on the system used to run the algorithms. It is meaningless to say that a given algorithm takes X instructions, since X depends on the CPU, the compiler, and so on. However, in some cases we ...


2

A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia: A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one ...


2

Having $n-1 \gt \sqrt{n}$, when $n \gt 3$ we can write $$\log (n-1) \gt \log \sqrt{n} = \frac{1}{2}\log n$$ So, taking $N=3$ and $C=\frac{1}{2}\gt 0$ we fulfilled definition for $\Omega$.


2

As you have seen, $\log(n+1) \in \mathcal{O}(\log n)$. That means that $\log n \in \Omega(\log( n + 1))$. Now you can change $n$ with $n-1$ and have your answer. To be more precise, $\log(\alpha n^{\beta} + \gamma) \in \Theta(\log n)$ for any $\alpha, \beta, \gamma \in \mathbb{R}_{>0}$.


2

This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$. The reduction Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$. Now, we define $M$ to be with $2n$ values, ...


1

Edit: This proof is insufficient as pointed out in comment. I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree. Since the heap is a complete tree, it means that its leaves are all on ...


4

$\DeclareMathOperator{\fib}{fib}$If you choose to calculate $\fib(n)$ by using the naive recursion formula, then you need $\Theta (\fib(n))$ additions, and since the numbers involved grow to $c\cdot n$ bits for a not very large constant $c$, it will take $\Theta(n \cdot \fib(n))$ operations. (I may be wrong here because most of the numbers involved may be ...


0

I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler. In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we want to know precisely ...


0

It’s obvious that recfunc(n) + 1 if n <= 3, then if n <= 6, n <= 12 etc. So recfunc(n) = 1 for all b, so we can calculate it in O(1).


2

Notice that the outer RecFunc call is just a "decoy" thrown in there to make the exercise seem more complicate than it is. Indeed, it is irrelevant as far as the asymptotic time complexity is concerned. This is because every call to RecFunc eventually returns $1$ (that's the only possible returned value, you can prove by induction that RecFunc ...


0

The number of multiplications in the algorithm is $2n - 1$, but the number of multiplications in the Horner's method is $n$, which means this algorithm is not optimal. As mentioned in the Wiki page, Horner's method in evaluating a polynomial is optimal, therefore we can change this algorithm so that it uses the Horner's method. p = a[n] for i = n-1 to 0: ...


3

As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$). You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the ...


1

Let $n = 3^{k}$ to obtain $T(3^{k}) = 9T(3^{k-1}) + 9^{k}$. This can be written $t_{k} - 9t_{k-1} = 9^{k}$. The characteristic equation is $(x-9)^{2} = 0$. Hence $t_{k} = c_{1}9^{k} + c_{2}k9^{k}$. Putting $n$ back instead of $k$, we find $T(n) = c_{1}n^{2} + c_{2}n^{2}\log_{3}n$. $T(n)$ is therefore $\Theta(n^{2}\log_{3}n)$.


0

You can find the definitions of big O notations on Wikipedia. They agree with your definition of big $\Theta$. As for your actual question, the answer is actually quite subtle. Sometimes it is possible to find constants $c_1,c_2,n_0$ which work for all values of the parameters. For example, in your case, all $n \geq 1$ satisfy $$ 1 \cdot n^{\max(a,b)} \leq n^...


0

Worse-case complexity gives an upper bound on the complexity of an algorithm in terms of some parameters. Often the parameter is the length of the input, either in bits or in words, but sometimes several parameters are pertinent. The standard example is graph algorithms, where complexity is often expressed in terms of both the number of vertices and the ...


0

I suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$ i.e. $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$. Proof: Let's consider $\phi \in O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \...


0

If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)). Though, saying O(max(n) + n) in O notation means O(max(n)) So it will still be accurate, since in both outcomes the Complexity is linear in the given input.


0

You can expand the recurrence $T(n) = 4T(n/2) + n^2 \log n$ directly: \begin{align} T(n) &= n^2 \log n + 4T(n/2) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16T(n/4) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16(n/4)^2 \log(n/4) + 64T(n/8) \end{align} and so on. We can simplify the terms: they are $n^2 \log n$, $n^2 \log(n/2) = n^2 (\log n - 1)$, $n^2\...


1

Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited. In the first version of your code, every room of the second kind will be put into the queue 3 times. In the second version of your code, every room of the second kind will be put into the queue only 1 time (except possibly ...


15

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting. What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform ...


3

Consider the language of all binary words which consist only of zeroes. It can be decided on a deterministic Turing machine in time $O(n)$, but not in time $o(n)$. For general time-constructible functions $f(n)$, the time hierarchy theorem shows that the problem of deciding whether a Turing machine halts in time $f(n)$ can be solved in time $O(f(n)\log f(n))$...


3

I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see. Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a ...


1

If you want to write the code with minimum time complexity, and you ask about it here, then you can't write it. If you ask about the simplest code with a better than quadratic time complexity, look up the Karatsuba method for fast multiplication, and possibly the Toom-Cook method. In principle, the fastest square root algorithm and the fastest multiplication ...


1

D.W.'s suggestion is absolutely worth doing if you expect the answer to be "false" a significant proportion of the time. With very little effort, you will be able to calculate most of the "no" answers quickly. You're not really asking about the complexity of computing a square or a square root, because the problem that you're actually ...


0

If $f(n) = O(A(n))$ and $g(n) = O(B(n))$ then $f(n) + g(n) = O(A(n) + B(n)) = O(\max(A(n),B(n))$. These are standard properties of big O, which follow almost directly from the definitions.


1

There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$. Do this a few times for a few random primes $p$. (You can even pick a random number $p$ without requiring it be prime.) If there is any error in your square root, then it is likely that it will be detected by this test. The chances of failing to ...


0

1- Because what the authors did in the end as preprocessing is compute p (decimal value of pattern P[1....m]) and the first value for the ts (aka tₒ), each/both of which can be done in $O(m)$. The remaining $n-m$ ts are then computed during matching time with each being $O(1)$. You can confirm this by looking at the code: 2- We might as well use this to ...


1

Using L'Hôpital's rule: $$ \lim_{n \to \infty} \frac{n^{1/10}}{\log n} = \lim_{n \to \infty} \frac{\frac{1}{10} n^{-9/10}}{n^{-1}} = \lim_{n \to \infty} \frac{n^{1/10}}{10} = +\infty. $$


3

The answer is actually subtler than it looks. Let us first consider a naive compiler. This naive compiler will implement the recursive case of $g$ by actually running $g(n-1)$ twice. The recurrences for the running time will be \begin{align*} T_f(n) &= T_f(n-1) + O(1) & T_f(1) &= O(1), \\ T_g(n) &= 2T_g(n-1) + O(1) & T_g(1) &= O(1), \...


2

Wolfram Alpha is giving you a more accurate estimate, $T(n) \sim 2n$. However, it can also give you the weaker estimate $T(n) = O(n)$ you are after: Just click on Show weaker bound.


Top 50 recent answers are included