Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

111 questions
15k 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 ...
8k views

9k 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 ...
1k views

293 views

Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
2k 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 ...
348 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,...
4k views

421 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 ...
317 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 ...
3k views

Does ln n ∈ Θ(log2 n)? [duplicate]

Is that statement false or true? I believe it's false because ln(n) = log base e of n. So therefore, log base 2 of n can be a minimum because in 2^x = n, x will always be less than y in e^y = n. ...
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)$ ...