Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,006 questions
Filter by
Sorted by
Tagged with
169 views

### d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
82 views

### A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
103 views

70 views

### Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?

On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to $$\text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1)$$ where $T$ is the ...
94 views

### Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
52 views

11k views

### O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
83 views

### Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
87 views

### Big O Notation Simplification in the fraction form

How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also ...
24 views

### Big O analysis trying to follow a logic

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
102 views

### Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is? My attempt: Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$ But given answer is $O(n)$. ...
753 views

### What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
575 views

### How come O(n) + O(logn) = O(logn)

How come O(n) + O(logn) = O(logn)? When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
153 views

### Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...
107 views

### Big-O in computer Science [duplicate]

As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
49 views

### Is this a valid use of big-O notation?

Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results. ...
69 views

### What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?

Consider the recurrence $$T(n,m) = T(n,m-1) + T(n-1,m) + c,$$ with base cases $T(n,0) = T(0,m) = 1$. This is the complexity of a recursive algorithm for the longest common subsequence, I know that ...
138 views

### How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?

$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$. I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess ...
96 views

### Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
32 views

### Prove that different definitions of big-Oh with n>=1 or n>N are equivalent

I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other: Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ...
51 views

### Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$

Given is the following recurrence relation: $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$ where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$. I'm ...
977 views

### Is “super-exponential” a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
82 views

### Does big-Oh notation in optimization follow the same convention as in CS?

I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. Now I am doing a project on optimization. In our optimization class, we ...
30 views

### Showing $2^x$ is a lower bound

How do I show that $2^x - x^2 \in \Omega(2^x)$? Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$. I worked around a bit with ...
1k views

### big-O and Θ notation subset

I was reading “Introduction to Algorithms” by CLRS and it says Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we ...
23 views

### Big O order of a function

I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working. My answer is O(n^2) ...
46 views

### How to find sets of polynomially bounded numbers whose subset sums are different?

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
54 views

### How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ? Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
63 views

### Big O and constants [duplicate]

I've already asked this question on stack overflow, but guys have suggested me to ask my question here. Let's consider classic big O notation definition (proof link): The $O(f(n))$ is the set of all ...
133 views

### Is the runtime of binary search big omega of logarithm of n?

My question is that can we say that runtime of the binary search is $\Omega(\log n)$? I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
120 views

### Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
100 views

### Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$. Find ...
9k views

177 views

### How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) [duplicate]

I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.
60 views

### Asymptotic growth of $\log(n^n + n)$

I would like to know if my understanding of this is correct: The question asks to show that the Big-Oh of the following function is $O(n\log(n))$ $$\log(n^n + n)$$ I think the first step is to ...
2k views

### Justification for neglecting constants in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
102 views

### Asymptotic Notation Analysis

2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1 since 2^n may or not be element of O(3^n) I need a hint to figure the problem
30 views

### Why is max{n,k}= Ө(n+k) [duplicate]

I saw this relationship in my exercise. max{n,k}= Ө(n+k) Could somebody prove it?
### Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? [duplicate]
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $k$ ...