# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,464 questions
Filter by
Sorted by
Tagged with
11 views

### Recurrence relation simplification

I have initial condition $π_1=2, π£_1=1$, and the given recurrence relations: $π_{π+1}=2π_π,$ $π£_{π+1}=2π£_π+\frac{1}{2} π_π$ I need to show that that, $v_i=\Theta(n_i\logβ‘ n_i).$ I observe ...
• 113
78 views

### How to simplify $O(\log (n!))$?

I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
• 23
49 views

• 183
1 vote
110 views

### Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?

We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the ...
• 53
1 vote
58 views

### Solving recurrence by iteration, choosing base case

A question I am to answer wants me to find the big O of a recurrence, I am doing it with the iteration method. For the base case, which we get after applying the recurrence $i$ times, can we make this ...
38 views

I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information. For context, I believe I've understood the formal ...
• 113
272 views

### Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

Is the time complexity of for(int i=0;i<n;i++){i*=k;} $O(\log_k n)$? The problem is number 8 from GeeksForGeeks: https://www.geeksforgeeks.org/practice-...
33 views

### Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
• 21
394 views

### Asymptotics of the sum of a geometric series

I have a parameter $q$ which is the probability of selecting a vertex (among $n$ vertices...) to be in a certain set. I am constructing the sets in an iterative way, having the vertex $v_i$ be in the ...
• 125
1 vote
165 views

### Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University. I have recently got through three questions I found in an old exam: Is it possible to sort in asymptotically linear time ...
• 13
1 vote