# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,235 questions
Filter by
Sorted by
Tagged with
0answers
10 views

### asymptotic (big-O) growth and asymptotic (omega-Ω) growth [closed]

Sort all the functions below in increasing order of asymptotic (big-O) growth. If some have the same asymptotic growth, then be sure to indicate that. As usual, lg means base 2. 1)5n
1answer
72 views

### Searching in sorted array with $O(\log n)$

Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows: Suppose array $A[1..n]$ consist of $n$ distinct integers that is ...
0answers
37 views

### Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
1answer
23 views

### Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
1answer
33 views

3answers
54 views

### Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$

having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function ...
1answer
20 views

### Computational indistinguishability for any distribution using a Chernoff bound

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
1answer
18 views

### What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
1answer
37 views