Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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