New answers tagged

0

Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think): $$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$ Now $f(n) = c\cdot g(n) + O(g(n))$ means, that $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have $$...


2

In this context, this comparison means the subset of. Hence, $O(n\log n) > O(n)$ means All members of $O(n)$ exist in $O(n \log n)$ as well or $O(n) \subset O(n \log n)$. For example, $f(n) = \sqrt{n} \in O(n)$ and $f(n) \in O(n\log n) $ and $g(n) = n \log n \not \in O(n)$ and $g(n) \ \in O(n \log n)$.


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


0

If I understand correctly, that you denote $n$=list.length and are calculating amount of "list[i] +=" operation. Then of course, as it is triple loop, then for $n$ times fixed "i" from first loop you take $n$ times "j" from second loop and $n$ times "k" from most inner, third, loop. So operation "list[i] +=&...


1

Firstly let me bring little more exactness. In sentence If I understood this definition right, it would mean that I can say; for a function $f(n) = n$ then $n$ is big-oh of $n^2$ because $n \leq 1\cdot n^2$ for any $n_0$. is used "any $n_0$", but in definition of $O$ we have $\exists n_0$ - existence is essential. To clear your doubts, hope, ...


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

Here’s a simpler approach than those suggested in the comments. Let $f(n) = 3n^3-6n^2+9n-9\log{n}$. We wish to show $f(n) \in \Theta(n^3)$. It suffices to show $f(n) \in O(n^3)$ and $f(n) \in \Omega(n^3)$. Big O: We wish to show $\exists c, n_0 > 0$ such that: $f(n) \leq cn^3$ $\forall n >n_0$. Let $n_0 = 1.$ We have: $f(n) = 3n^3-6n^2+9n-9\log{n} \leq ...


1

The statement $n = O(n^2)$ is true. There is nothing wrong with it. Maybe you're thinking of the Theta notation.


2

for(i=1;i<=n;i++) { for(j=1 ; j <= i*i ; j++) { for(k=1 ; k<= n/2 ; k++) { x = y + z; } } } The triple-nested loop is equivalent to the summation $$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \...


0

Let the probability that the key is found be $p$. Then in case of a miss (probability $1-p$), we perform $n$ comparisons, in case of a hit (probability $p$), we perform from $1$ to $n$ comparisons with equal probability. Hence the expected number of comparisons is $$(1-p)n+\frac{n+1}2p=\frac{(2-p)n+p}2.$$ In Landau's asymptotic notation, this is $\Theta(n)$...


0

Let us recall the definition of big-O notation. If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n > n0, 0 ≤ g(n) ≤ c f(n) Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 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

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

You know T(n, C) for all n. I’d try to determine T(n, C-1) for all n, then T(n, C-2) and so on.


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


2

In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$. Assume that $0<C<n$. Show that $$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$ for $0\leq k\leq n-C$ and $n\leq 2C$. It looks like this is the formula that you mentioned in the question, except that the binomial coefficient should have the same amount that is ...


Top 50 recent answers are included