Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
91
votes
3answers
23k views

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
89
votes
11answers
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 ...
61
votes
9answers
6k views

Are there any problems that get easier as they increase in size?

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...
51
votes
5answers
7k views

How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers: ...
46
votes
10answers
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)$ ...
44
votes
2answers
3k views

What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
39
votes
4answers
6k views

What is the name the class of functions described by O(n log n)?

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"): O(1) is "Constant" O(log n) is "Logarithmic" O(n) is "Linear" O(n^2) is "Quadratic" O(n * log n) ...
35
votes
6answers
9k views

Sorting functions by asymptotic growth

Assume I have a list of functions, for example $\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$ How do I sort them asymptotically, i.e. after the relation defined by $\qquad f \leq_O g \...
32
votes
2answers
1k views

How asymptotically bad is naive shuffling?

It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly: ...
31
votes
4answers
41k views

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
27
votes
1answer
876 views

Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
25
votes
10answers
6k views

“For small values of n, O(n) can be treated as if it's O(1)”

I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1). Example: The motivation for doing so is based on the incorrect idea that O(1) ...
25
votes
2answers
5k views

Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
23
votes
4answers
2k views

How to fool the plot inspection heuristic?

Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is ...
23
votes
5answers
9k views

Is O(mn) considered “linear” or “quadratic” growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
21
votes
1answer
720 views

What are the first computer science papers that used asymptotic time complexity?

When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, Big Omicron and Big Omega And Big Theta, SIGACT April-June 1976, but the ...
19
votes
2answers
7k views

Changing variables in recurrence relations

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations. The following method can be illustrated with this ...
19
votes
1answer
634 views

Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
18
votes
7answers
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 ...
18
votes
2answers
3k views

Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$

Construct two functions $ f,g: R^+ → R^+ $ satisfying: $f, g$ are continuous; $f, g$ are monotonically increasing; $f \ne O(g)$ and $g \ne O(f)$.
16
votes
5answers
14k views

Solving a recurrence relation with √n as parameter

Consider the recurrence $\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$ for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$. I know the Master theorem for ...
16
votes
1answer
300 views

Are asymptotic lower bounds relevant to cryptography?

An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
15
votes
3answers
5k views

Solving Recurrence Equations containing two Recursion Calls

I am trying to find a $\Theta$ bound for the following recurrence equation: $$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$ I figure Master Theorem is inappropriate due to differing amount of ...
15
votes
4answers
3k views

Are the functions always asymptotically comparable?

When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the ...
15
votes
4answers
528 views

What does $\log^{O(1)}n$ mean?

What does $\log^{O(1)}n$ mean? I am aware of big-O notation, but this notation makes no sense to me. I can't find anything about it either, because there is no way a search engine interprets this ...
15
votes
2answers
14k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
14
votes
3answers
620 views

What goes wrong with sums of Landau terms?

I wrote $\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$ but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also ...
13
votes
6answers
19k views

n*log n and n/log n against polynomial running time

I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\...
13
votes
2answers
640 views

Do non-computable functions grow asymptotically larger?

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all ...
13
votes
1answer
863 views

Algorithms with O(sqrt(N)) SPACE complexity?

Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.
12
votes
2answers
24k views

What is an asymptotically tight upper bound?

From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation. But what does asymptotically tight upper bound mean for Big-O notation?
12
votes
2answers
458 views

Infinite chain of big $O's$

First, let me write the definition of big $O$ just to make things explicit. $f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$ Let's say we have a finite ...
11
votes
2answers
481 views

How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

This a homework question from Udi Manber's book. Any hint would be nice :) I must show that: $n(\log_3(n))^5 = O(n^{1.2})$ I tried using Theorem 3.1 of book: $f(n)^c = O(a^{f(n)})$ (for $c >...
11
votes
2answers
258 views

Is $O$ contained in $\Theta$?

So I have this question to prove a statement: $O(n)\subset\Theta(n)$... I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\...
11
votes
2answers
2k views

Simplify complexity of n multichoose k

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$ ...
11
votes
1answer
1k views

Asymptotic Analysis for two variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
11
votes
2answers
11k views

Master theorem not applicable?

Given the following recursive equation $$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that $$ n^{\log_2(2)} = n.$$ Now we check the first two cases for $...
10
votes
3answers
630 views

Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$ T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n $$ $$ T(n) \leq 2\left(c\left\...
10
votes
2answers
932 views

How to discuss coefficients in big-O notation

What notation is used to discuss the coefficients of functions in big-O notation? I have two functions: $f(x) = 7x^2 + 4x +2$ $g(x) = 3x^2 + 5x +4$ Obviously, both functions are $O(x^2)$, indeed $\...
10
votes
1answer
5k views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
10
votes
1answer
439 views

Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)

Suppose an algorithm has a runtime recurrence relation: $ T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 ...
10
votes
3answers
668 views

Sums of Landau terms revisited

I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success. Now, over here our recurrence guru JeffE ...
10
votes
4answers
331 views

Example of an algorithm where a low-order term dominates the runtime for any practical input?

Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge. Are there any known ...
9
votes
5answers
7k views

What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
9
votes
3answers
6k views

What does it mean by saying “Asymptotically more efficient”?

What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ? $X$ will be a better choice for all inputs. $X$ will be a better choice for all inputs except small ...
9
votes
2answers
736 views

2-D peak finding complexity (MIT OCW 6.006)

In a recitation video for MIT OCW 6.006 at 43:30, Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to ...
8
votes
2answers
1k views

Double exponentials vs single exponentials

Here are four tenets I cannot reconcile: Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
8
votes
3answers
1k views

Why is $3^n = 2^{O(n)}$ true?

$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2. How is $3^n = 2^{O(n)}$ true?
8
votes
3answers
159 views

Upper bound of of fib(n+2)

I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper ...
8
votes
4answers
1k views

Nested Big O-notation

Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$. It feels natural to write that the running time on this graph would be $O(O(V^2)+...