# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

117 questions
Filter by
Sorted by
Tagged with
17k views

### Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
9k views

10k views

4k views

### The order of growth analysis for simple loop

What would the order of growth for this loop be: int sum = 0; for (int n = N; n > 0; n /= 2) for(int i = 0; i < n; i++) sum++; The first loop ...
391 views

### Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst case,...
3k 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 ...
1k views

3k views

### Show that $\log n = o(n^\epsilon)$

I am trying to understand how to prove that a polynomial will always grow faster than a logarithm. $\log n = o(n^\epsilon), \epsilon>0$ Intuitively, it is obvious, and plugging in a few numbers ...
298 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
4k views

432 views

### Relationship between an integer N and the number of bits n required to represent the integer

I'm trying to understand the time complexity of the following code in terms of n. Pseudocode for trial division: I understand that the time complexity of the algorithm is O(sqrt(N)). However, can ...
687 views

### Asymptotic relationship of logarithms in different bases

I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true). For the functions $\lg n$ and $\log_8 n$, what is the ...
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)$ ...