Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
1
vote
1answer
19 views

Proving that $S_1+S_2 \leq f^{-\omega(1)}$

I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...
0
votes
1answer
28 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
1answer
63 views

How to justify $f(n) = O(g(n))$ [duplicate]

The following question is in my homework: Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$? I understand how $f(n)$ is the upper bound of $g(n)$. ...
0
votes
0answers
18 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
20 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 ...
1
vote
1answer
52 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 ...
4
votes
1answer
66 views

Exact meaning of $2^{\mathcal{O}(f(n))}$

In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time. For example he says that the running time of a single-tape ...
1
vote
1answer
47 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 ...
2
votes
1answer
18 views

Asymptotic Relationship from Limit

F(n) = n-100 G(n) = n-200 I am trying to show the asymptotic relationship between these two functions using limits. I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c. ...
-2
votes
1answer
26 views

Help with Big-O homework [duplicate]

"er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct.
3
votes
2answers
148 views

Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following: $$ \sum_{i=1}^n O(i) $$ is not the same as (I'm not using DNE because the book explicitly ...
2
votes
1answer
54 views

O(1) distinct elements in an array implies?

Could someone explain the following question - Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that the array has only O(1) distinct elements. ...
0
votes
1answer
18 views

When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?

Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $ O(n^2) $ algorithm actually runs slower than before. Is this the correct idea when a ...
0
votes
1answer
17 views

Why does Union-Find have time complexity O(N + M lg* N) with the “log star N”?

The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be $$ O(N + M \lg^*N) $$ and the $ lg^*N $ is "log star N" and is iterated logarithm. ...
3
votes
1answer
203 views

Basic Theta-notation question

Let $T$ be a function. Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$ Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$? In words: is such a case, is there a function ...
3
votes
5answers
7k views

How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive. I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for ...
-1
votes
0answers
15 views

What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?

Is it true that some common forms of recursive T(n) can give the following conclusions? When T(n) = T(n/c) + b where c is a constant > 1, b is any constant ...
1
vote
1answer
39 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 ...
3
votes
2answers
175 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 ...
4
votes
1answer
577 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
1
vote
3answers
2k views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
1
vote
1answer
574 views

How to find kth largest element in (max) priority queue in O(m) time?

Here is my exercise. FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
1
vote
0answers
21 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 ...
3
votes
2answers
54 views

Struggling to understand the symbolism around the big oh formal definition

I'm struggling to understand what exactly T(n), and f(n) is in the above text: When we compute the time complexity T(n) of an ...
0
votes
0answers
11 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
1answer
55 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
2
votes
1answer
54 views

runtime of 2 dependent nested for loops [duplicate]

for (i=1; i<=n ;i=i*2){ for (j=1; j<=i ;j++){ basic_step; } } Regarding the above nested loops, I can't seem to understand why is the following ...
0
votes
3answers
63 views

Is there a unit of measurement that can express code execution speed in absolute terms?

I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
1
vote
1answer
22 views

Time complexity of rotation array m times using temporary array

I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the ...
1
vote
1answer
60 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
0answers
136 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
16 views

Proof involving asymptotic complexity

The question in Proof of big-o propositions asked to prove: $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$ The accepted answer starts the proof with: Suppose that $...
1
vote
1answer
27 views

Akra-Bazzi method integral diverges

I want to solve this recursion: $$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$ My attempt and issue: None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en....
1
vote
1answer
29 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
1
vote
0answers
22 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(...
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 ...
1
vote
2answers
55 views

Average case analysis of linear search

Based on CLRS question 2.2: Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to ...
3
votes
1answer
55 views

The role of asymptotic notation in $e^x=1+𝑥+Θ(𝑥^2)$?

I'm reading CLRS and there is the following: When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1+𝑥+Θ(𝑥^2)$$ I suppose I understand what means this equation from math ...
61
votes
9answers
6k views

Are there any problems that get easier as they increase in size?

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...
1
vote
2answers
118 views

Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?

This is a question posted for extra practice (i.e., not for credit): Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain. I'm not sure ...
2
votes
2answers
87 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
2
votes
2answers
39 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
1
vote
1answer
58 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
0
votes
1answer
48 views

What impact does the modulo operator have in a for-loop?

Here's an example of what I mean: ...
3
votes
1answer
13k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
31
votes
4answers
41k views

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
5
votes
2answers
608 views

Confusion with analysis of hashing with chaining

I was attending a class on analysis of hash tables implemented using chaining, and the professor said that: In a hash table in which collisions are resolved by chaining, an search (successful or ...
1
vote
1answer
26 views

Comparing different asymptotic notations

Suppose we have 3 algorithms complexity times at the worst case: A = $O(nlogn)$ B = $O(n\sqrt{n})$ C = $\Theta(n)$ In my opinion, it is not possible to define the best solution, since we don't know ...
0
votes
1answer
31 views

Trouble finding what this recurrence solves to [duplicate]

I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$ I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
3
votes
2answers
156 views

Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...