Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.
1
vote
2answers
46 views
Solving a recurrence
Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution....
I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) ...
1
vote
1answer
11 views
Immediate positions algorithm?
Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?.
Given a set $X$ and $z$ not in $X$, indicate ...
-1
votes
0answers
31 views
How to prove the worst case complexity of an algorithim is $O(g(n))$, where $g(n)$ is some function [duplicate]
I'm learning algorithms and complexities and I'm quite confused at this point. Im using to proving things like $f(n) = O(g(n))$ where I have clear definitions for both $f(n)$ and $g(n)$.
Now I have a ...
1
vote
2answers
93 views
Are the following loops $O(n^2)$ complexity
I'm presented with two snippets of code, and I need to determine their time complexity. I'm pretty convinced that both of these are $O(n^2)$, but I'm not 100% sure
1.)
2.)
0
votes
1answer
13 views
FFT for expanded form of equation multiplication
I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?
For example, if you are multiplying ...
2
votes
1answer
20 views
Running time and stack depth of a lisp recurrence
Consider the following sequence $a_n$:
\begin{align*}
a_0 &= \alpha \\
a_k &= \beta a_{k-1} + \kappa
\end{align*}
Now consider the implementation of this sequence via lisp:
...
2
votes
2answers
51 views
How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?
I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ...
8
votes
0answers
86 views
Do functions with slower growth than inverse Ackermann appear in runtime bounds?
Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...
3
votes
0answers
50 views
Expected depth of modified kind of treap
If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
3
votes
1answer
56 views
Evaluating recurrence relation
Suppose an algorithm has a runtime recurrence relation:
$ T(n) = \left\{
\begin{array}{lr}
g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\
f(n) & : n < n_0
...
-2
votes
0answers
26 views
Tell wether following algorithms are parallelized or not? [duplicate]
Analyze that whether the following sorting algorithm perform better if they run on “n” number of processors.?
Analyze that whether the following sorting algorithm perform better if they
run on “n” ...
2
votes
0answers
48 views
A comparison between Aho-Corasick algorithm and Rabin-Karp algorithm
I am working on multiple patterns search matching algorithms and I found that two algorithms are the strongest candidates, namely Aho-Corasick and Rabin-Karp in terms of running time. However, there ...
-1
votes
1answer
62 views
Time Complexity of Algorithm
I need help with finding out the time complexity of the following algorithm:
...
2
votes
1answer
45 views
Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?
In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
2
votes
1answer
47 views
Do different variants of Mergesort have different runtime?
One of my courses introduced the following question:
Given the recurrence relation for mergesort:
$T(n) = 2T(n/2) + n$
How would the following parameter passing strategies influence the ...
