New answers tagged

0

$$T(n)= 5T\left(\frac{n}{4}\right) + n^2 = 5^2T\left(\frac{n}{4^2}\right)+\left(\frac{5}{16}+1\right)n^2=\\=5^3T\left(\frac{n}{4^3}\right)+\left(\left(\frac{5}{16}\right)^2+\frac{5}{16}+1\right)n^2=\cdots=\\ =5^kT\left(\frac{n}{4^k}\right)+\left(\left(\frac{5}{16}\right)^{k-1}+\cdots +\frac{5}{16}+1\right)n^2$$ If you have some initial condition for $T(1)$ ...


1

This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions: Global optimization - a branch of numerical analysis, that deals with various iterative algorithms, able to find ...


1

Some answers suggest using the logarithm of n. Now guess what is the first thing your computer does if you try to calculate log n: It converts n from an integer to a floating point number, and from the exponent of the floating point number you get the number of bits immediately. So whatever time complexity there is, you have spent it already before even ...


0

N is 4 and b is 3. The formula holds perfectly fine. Nothing is wrong. The reason to "round up" in the context of the numbers you have is because of the inequality. 2 would not satisfy x ≥ ~2.32. But 3 would.


2

The number of bits is always an integer, so you have to solve for that equation over the integers. Thus, use $\lceil \lg (n+1) \rceil$.


0

If you want to generate a list of $n$ random codes, from a space of at least $2n$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat. The running time will be $O(n)$. This is the method you have rejected in the question. If you want to generate ...


1

If you want an algorithm that is always correct you can not do better, precisely because you have to look at all the values at least once (except if you find a $0$ somewhere, then you can immediately return that). Otherwise, suppose your run your algorithm $A$ some input $I=[a_1,a_2,\ldots,a_n]$, and it returns a value $v\neq 0$ without looking at all ...


0

Your constant $c$ needs to satisfy $$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$ that is, $$ \frac{5}{16} c + 1 \leq c. $$ Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.


2

It's well known task "Checking for Duplicates" and you can found it for example in Tim Roughgarden - Algorithms Illuminated_ Part 1_ The Basics-(2017) 42 page. Let me say, that as here so in book taking last index "i" as $n=$"array.length()" have no sense, because then index "j" runs out of borders. But this do not ...


2

The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input. In your case, the size of the input is at least $n$ (...


0

By definition $O(g)$ should be always defined variable and limit point with respect to is considering $O$. For example in $O(n^3), n \to \infty$ variable is $n$ and limit point $\infty$. In $O(x^3), x \to 0$ variable is $x$ and limit point $0$. So when we write $f=O(g)$, then formally we mean some variable and some limit point. For example $f(n)=O(g(n)), n \...


1

A better bound on the complexity is $O(k)$, where $k$ is the total number of files. A similar situation is encountered in algorithms for sparse matrices. Sparse matrices are stored as a list of all non-zero entries. The running time is often analyzed in term of the number of non-zero entries rather than the dimensions of the matrix. The reason is that ...


0

In DFS also the traversal sequence on the above graph will be A->B->C->B->A->D->A. It is just that it prints a node when it visits it first time and marks it as visited. In this case, it'll print A B C but when it again visits B and A it ignores it as it is already visited. Backtracking is a programming paradigm whereas DFS is an actual ...


1

Just to mention something in addition to the other (correct) answers: Such complexities can arise when the runtime of the algorithm depend on more than just one parameter / if one does not care about the input size. For example, searching the minimum in $n$ elements is clearly in $O(n)$, however, if you do this in parallel using $p$ processors, the ...


10

Try brute force searching of a key for a cryptographic algorithm. The more of the key you give it to start with, the less you have to search for. True that trend stops at the limit of keysize (but that's still monotonic), and there are probably other examples in the field of extensive search where the more input data, the easier it is to prune branches of ...


0

Just reading in the (full) input is $O(n)$ for input of size $n$.


8

Well an algorithm with $O(0)$ fulfills the criterion. It basically does nothing. As soon as your algorithm does at least one operation on execution it has a runtime cost $t(n) > 0$. Since $$t(n)\in O(1/n) \Leftrightarrow \exists c,n_0\forall n >n_0: t(n) \leq c\cdot\frac 1 n$$ An algorithm with constant runtime doesn't have runtime $O(1/n)$. This ...


1

Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a[12] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0. So if you have n integers, create a two dimensional array of size m * ...


4

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by all intersections of unit disks, ...


2

I believe the question is about time complexity without DP. I read somewhere that it was mentioned the complexity is $\mathcal O(m^n)$ but there is a much tighter bound that I will derive below. Based on the recursion relation we get $$ T(n) = \sum_{i=1}^m T(n-i) + m $$ where I have included the time for adding the results of the recursive calls. Now it ...


1

One way to convince yourself it is not possible is to consider what it would enable. Assume there exists an O(1) algorithm for insertion into an unbounded sorted array, CONST_INSERT. Then we can define a O(n) sorting algorithm as follows: Let $L$ be an empty list $()$ and $U = (u_1, u_2, \ldots u_n)$ be an unsorted list. Iterate over $i: 1 \rightarrow n$, ...


3

Suppose that the input alphabet is $\{0,1\}$, and consider the language $L_1 = 0^*$. We can easily construct a Turing machine $T_1$ such that $S_{T_1}(I) = |I|+1$. On the other hand, $S_{T_2}(I_c) \geq |I_c|+1$. Since $|I_c|=|I_1|+1+|I_2|$, we get $$ S_{T_2}(I_c) \geq |I_1|+1+|I_2|+1 = S_{T_1}(I_1) + S_{T_1}(I_2). $$


0

The computers on board Voyager 1 have been running for almost 43 years at the time of writing. I believe this holds the record for the longest uninterrupted uptime of any piece of software.


1

There have been several programs running for very long times, like the Great Internet Mersenne Prime Search, which has been going for some 25 years now.


0

You are right, the complexity of the second algorithm is $O(P)$ where $P$ is the depth of the given vertex in the second tree. Notice that, without additional assumptions, it might very well be $P=\Omega(N)$ (think, e.g., of a path rooted in one endpoint where the given vertex is the other endpoint). If the second tree is somehow "balanced", for ...


0

The outer most while loop ends when $\text{sq} = n$ and by definition $\text{sq} = i^2$ and thus it will run $i^2 = n \Rightarrow i = \sqrt{n}$ times ( as we increment $i$ by one each iteration). Note that - The for loop runs at $\log(j)$ from $1$ to $\text{sq} = i^2$ and $1 \leq i \leq \sqrt{n}$ so we have this sum: $$\sum_{k=1}^{i^2}\log(k) ~~ \forall i \...


0

Another example is the famous subset sum problem: There is an exponential-time algorithm that works in $O(2^{n/2} \textsf{poly}(n))$. There are also pseudopolynomial time algorithms working in $O(nt)$ (via dynamic programming) and $O(n+t)$ (the later one being a randomized algorithm). Depending on the input size, one can choose between different algorithms (...


0

The best answer I can think of is Shigeru Kondo running an algorithm for 371 days to compute the first 10,000,000,000,050 digits of pi. Link


4

For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection". If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 ...


2

This sequence is OEIS A173566. To understand how large it grows: $a_n = 2^{2^{b_{n-1}}}$ where: $b_0 = 0$ $b_n = b_{n-1} + 2^{b_{n-1}}$ The sequence $b_i$ grows faster than $2^{\cdotp^{\cdotp^{2^0}}}$, where there are $i$ 2's in the tower. EXPTIME is $O(2^n)$, 2-EXPTIME is $O(2^{2^n})$, and in general, you can define n-EXPTIME . The sequence $b_i$ is not in ...


0

The runtime in the original post is correct. The O(n) runtime is for a different algorithm, called optimized bubble sort.


0

You can compute the number of rounds by a recursive formula. Find an $i$ such that $i^i = n$. But we know that $i = 2^k$. Hence, we should find a $k$ such that $n =(2^k)^{2^k}$. Hence, $\log{n} = 2^k \log{2^k} = k \times 2^k$. Now, if we suppose $n = 2^m$, $m = k\times 2^k = i \log{i}$ and $n = 2^{i \log{i}}$. Hence, if we suppose $T(n)$ is the complexity of ...


0

There is no closed form. The number of loop iterations is 0 if n <= 2, 1 if n <= 4, 2 if n <= 256, 3 if n <= $2^{264}$, 4 if n is less than some number with more than $2^{264}$ digits, so the universe isn’t large enough to write that number down. The real problem is not the number of iterations, but how long it takes to calculate the last i, ...


0

Yes, but the only example I know is subsumption in FL$^-$, which actually is in P. On the other hand, subsumption in full FL is co-NP hard. A standard reference is Levesque and Brachman, Expressiveness and tractability in knowledge representation and reasoning. Here you can find more about FL$^-$, while these note are devoted to the computational complexity ...


0

As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link: DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of ...


Top 50 recent answers are included