Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
76
questions with no upvoted or accepted answers
6
votes
0answers
203 views
Are there master theorems that deal with parameters of the form $n-c$?
While thinking about this question on a recurrence I checked out some stronger master theorems.
Unfortunately, they do not seem to apply because terms
$\qquad\displaystyle T(n) = \dots + T(n-1) + \...
4
votes
2answers
225 views
Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
3
votes
0answers
47 views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
3
votes
0answers
93 views
Name for function in big O but not in little o?
Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
3
votes
0answers
1k views
Node potentials of minimum cost flow successive shortest path algorithm
I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
2
votes
1answer
65 views
Quickly obtaining sums of sets of numbers
We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
2
votes
0answers
38 views
Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution
What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?
2
votes
0answers
534 views
Can factorial be done in O(1) and proof?
The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, ...
2
votes
0answers
21 views
Is variance taken into account when algorithm analysis is performed?
Silly question. I was wondering if the measure of "variance" is taken into account when the analysis of an algorithm is performed (asymptotic). In general best-case,worst-case,average-case are taken ...
2
votes
0answers
212 views
Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?
I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that ...
2
votes
0answers
545 views
How to find all paths with n-distance from a node in a graph with cycles?
I have to find all the paths that have some n-distance from a start node. The destination node is not given. It seems that this problem is very hard to solve because in this scenario I am working with ...
2
votes
0answers
35 views
Examples of algorithms with low spacetime complexity
When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A ...
2
votes
1answer
46 views
Spotting the difference between two arrays using divide-and-conquer
Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.
For ...
1
vote
1answer
53 views
Analyzing time complexity of solution in tutorial
Could someone explain time complexity of solution of in this tutorial?
I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.
What I figured so far is, for ...
1
vote
0answers
22 views
Useful conditions for proving super polynomial lower bound for some kind of recurrences
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$
Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
1
vote
0answers
137 views
Approaches for analyzing the work, critical path length and parallelism
I'd like to know where to find references and approaches on how to analyze the work, critical path length and parallelism of algorithms.
In particular, for solving the type of homework problems below:...
1
vote
1answer
45 views
Recursion Time Complexity (Half n' Half)
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:
Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
...
1
vote
0answers
25 views
Cuckoo hashing with a stash: how tight are the bounds on the failure probability?
I was reading this very good summary of Cuckoo hashing.
It includes a result (page 5) that:
A stash of constant sizes reduces the probability of any failure to
fall from $\Theta(1/n)$ to $\Theta(...
1
vote
1answer
55 views
Interpretation of an asymptotic notation
Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
1
vote
0answers
83 views
What are the asymptotic bounds (upper bound on time complexity) of the following function?
I am trying to find the upper bound on time complexity of the recursive function defined by the following equation:
$$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
1
vote
0answers
62 views
Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?
Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n).
Can I say that θ(g(n)) is the intersection of these two sets?
...
1
vote
0answers
67 views
How to find big-O for an in-place perfect shuffle algorithm
I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
1
vote
0answers
28 views
What is the runtime of Quantum Fourier Sampling
I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves?
Either big-O or more accurate ...
1
vote
0answers
49 views
Can there be functions in o(1) in algorithm analysis?
I saw a similar question to this one here but it's not quite the same as mine:
Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?
I've just started a course in data structures and ...
1
vote
0answers
60 views
Order of growth: substitution of monotonically increasing functions
One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule.
$$
\lim_{n\...
1
vote
0answers
68 views
Verifying that $f(x) \leq Cg(x)$ for $x \geq k$
I'm revising for a test and having problems with a past question. It states that $f(x)=5x^2+4x+3$ is $O(x^2)$ and has a series of sub-parts asking if particular values of $C$ and $k$ (e.g., $C=12$, $k=...
1
vote
0answers
324 views
Why do we count the ceils and floors in recursive functions?
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\...
1
vote
0answers
67 views
Divide-and-conquer algorithm to takes a set of itineraries and returns desirable itineraries
I've been given a question that states I will be given a set of itineraries, which are basically tuples in the form (cost, time) for airplane flights. An itinerary dominates another itinerary if its ...
1
vote
0answers
146 views
Asymptotic Analysis of Sum
I want to do an analysis on the sum $ \Sigma_{i=0}^n f(i)$. All that is known about $f(i)$ is that $f(i) \in \Theta (i \log i ) $.
How do I do this?
1
vote
0answers
207 views
Is this Summary of Asymptotic Analysis Correct?
I'm one year through both an undergraduate CS and undergraduate math degree, currently studying Big-O analysis, and am trying to develop a "mental checklist" as it were, or a kind of procedural ...
1
vote
0answers
114 views
Proof that $n \log_2 n - n \log_2 e \in \Omega(n \log_2 n)$ (lower bound of sorting algorithms)
Regarding the last step of the proof of the lower bound of comparison based sorting, there is the following implication for the runtime T in my book:
$T \ge n \log_2 n - n \log_2 e \implies T \in \...
1
vote
0answers
172 views
Help understanding “little o” notation
I have the following homework problem, with given solution but I do not understand why certain choices in the solution were made as opposed to my own (incorrect) solution and I would like some ...
1
vote
0answers
363 views
Turing Machine that accepts $L=\{a^nb^n | n \geq 1\}$ with at most nlog(n) transitions in 1 tape
I'm having trouble trying to create this machine. I know the answer should go in the way that we always cut in half the number of a's and b's (so the master theorem aplied at $T(n)=T(n/2)+O(n)$ gives ...
1
vote
0answers
51 views
What is the difference between O(n^2) and O(N)[N*O(1)]?
I was reading this article on gperf.
In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
1
vote
0answers
134 views
Algorithm to find min pos difference between two integers in an array
The question I'm faced with:
Let $A[1], A[2], ...,A[n]$ be an array containing $n$ very large positive integers.
Describe an efficient algorithm to find the minimum positive difference between ...
1
vote
0answers
76 views
Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )
You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively.
Assume that you have to choose ...
1
vote
0answers
104 views
Why does $\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$?
I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far.
$\sum\...
1
vote
1answer
64 views
How to find an algorithm's complexity from actual running times
I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
1
vote
1answer
434 views
Solving T(n) = 2T(n/3) + 2 T(2n/3) + n
The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:
Recursion tree. We see that
$$\begin{align}
\sum_{...
0
votes
0answers
13 views
Detailed explanation of Perlin Noise algorithmic complexity
I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...
0
votes
0answers
26 views
proving long asymptotic bounds
I'm trying to find ways this simplify this formula and assuming numbers but that doesn't seem to help, the question is asking to prove or disprove:
$$ 3n(\log_{}n)^2 + 4n = \Omega (2n^2 \log_{}n +1) $...
0
votes
1answer
36 views
Find function that satisfy the relation
Can you find the function that satisfy the relation?
$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
0
votes
0answers
23 views
Time complexity of simple function related to bits
I am wondering about correct answer to this task from a yesterday's test:
A function Pow which calculates $y = a^k$ is given, where $k$ is an
integer of length ...
0
votes
0answers
23 views
Asymptotics and logarithms/exponents
We have four categories:
additive constants, multiplicative constants, polynomials, and
exponentials
When determining the growth order of functions, we only care about polynomials and ...
0
votes
0answers
12 views
Mapping every character to its next occurrence based on the number of unique characters between the occurrences
To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
0answers
31 views
Deducing $3^f = o(3^g)$ from $f = o(g)$
I really need help solving the following question:
Given:
$$f(n) = o(g(n))$$
Prove:
$$3^{f(n)} = o(3^{g(n)})$$
My attempt:
I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $.
I need to ...
0
votes
0answers
25 views
Calculating the Complexity of a Two Part Algorithm
This is in relation to this post I made. I eventually solved this by the following approach:
Take the un-ordered file with all the purchasing data and use the UNIX ...
0
votes
0answers
33 views
Minimization with asymptotic assumption
Given the function
$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with}
\left\{\begin{matrix}
a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\
b\leq a! \\
c\leq (n-a)! \\
\end{matrix}\right.
\Big\}...
0
votes
1answer
30 views
Is this computational complexity of the k-NN (custom distance) correct?
I read on a book that in general k-NN (no optimizations), given
$d$ dimensions
$n$ examples
every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
0
votes
0answers
32 views
Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?
Given this naive recursive function:
...
