Skip to main content

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
101 votes
3 answers
35k 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 ...
Miles's user avatar
  • 1,323
98 votes
11 answers
29k 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 ...
Raphael's user avatar
  • 72.6k
69 votes
9 answers
7k 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 ...
dsaxton's user avatar
  • 923
56 votes
5 answers
8k 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: ...
Anthony Rossello's user avatar
53 votes
4 answers
7k 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))$. ...
Frank's user avatar
  • 1,642
49 votes
4 answers
72k 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. ...
Smajl's user avatar
  • 1,045
48 votes
10 answers
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)$ ...
doubleE's user avatar
  • 591
41 votes
6 answers
20k 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 \...
JAN's user avatar
  • 619
41 votes
4 answers
11k 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) ...
GlenPeterson's user avatar
33 votes
2 answers
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: ...
Steven Stadnicki's user avatar
29 votes
5 answers
21k 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" (...
user541686's user avatar
  • 1,167
29 votes
1 answer
1k 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 ...
Yuval Filmus's user avatar
27 votes
2 answers
6k 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 ...
A T's user avatar
  • 968
27 votes
2 answers
5k views

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
mariaprsk's user avatar
  • 411
26 votes
11 answers
8k 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) is ...
rianjs's user avatar
  • 373
25 votes
4 answers
3k 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 ...
Raphael's user avatar
  • 72.6k
25 votes
7 answers
6k views

Justification for neglecting constant factors 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 ...
gpuguy's user avatar
  • 1,799
23 votes
2 answers
11k 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 ...
erickg's user avatar
  • 331
23 votes
1 answer
899 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 ...
dan's user avatar
  • 529
20 votes
1 answer
15k 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 ...
corsiKa's user avatar
  • 423
20 votes
2 answers
7k 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)$.
Jessie's user avatar
  • 333
20 votes
1 answer
1k 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 ...
Raphael's user avatar
  • 72.6k
19 votes
3 answers
22k 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 ...
user avatar
18 votes
5 answers
5k 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 ...
user avatar
18 votes
3 answers
52k 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?
Vivek Kumar's user avatar
18 votes
5 answers
23k 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 ...
seeker's user avatar
  • 283
16 votes
3 answers
13k 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 ...
Laura's user avatar
  • 544
16 votes
2 answers
12k views

Difference between the tilde and big-O notations [duplicate]

Robert Sedgewick, at his Algorithms - Part 1 course in Coursera, states that people usually misunderstand the big-O notation when using it to show the order of growth of algorithms. Instead, he ...
thyago stall's user avatar
16 votes
1 answer
390 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 ...
Micah Beck's user avatar
15 votes
4 answers
719 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 ...
Oebele's user avatar
  • 253
15 votes
6 answers
34k 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/\...
mihsathe's user avatar
  • 251
14 votes
3 answers
6k views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
user avatar
14 votes
3 answers
1k 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 ...
Raphael's user avatar
  • 72.6k
14 votes
3 answers
10k views

Is "super-exponential" a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
Covi's user avatar
  • 243
14 votes
2 answers
948 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 ...
hollow7's user avatar
  • 527
13 votes
4 answers
32k 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 ...
Garrick's user avatar
  • 472
13 votes
1 answer
2k 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.
vawd_gandi's user avatar
13 votes
1 answer
3k 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 ...
sas's user avatar
  • 133
12 votes
5 answers
6k views

Does it make sense to say Big Theta of 1? Or should we just use Big O?

Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$? Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
MattCochrane's user avatar
12 votes
2 answers
573 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 ...
mrk's user avatar
  • 3,708
12 votes
2 answers
3k 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$ ...
yoniLavi's user avatar
  • 245
11 votes
6 answers
12k 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 ...
Robert S. Barnes's user avatar
11 votes
2 answers
715 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 >...
Andre Resende's user avatar
11 votes
3 answers
3k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
Carter Falkenberg's user avatar
11 votes
2 answers
317 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)\...
Rawb's user avatar
  • 245
11 votes
2 answers
21k 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 $...
Joachim's user avatar
  • 213
10 votes
3 answers
793 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\...
Erb's user avatar
  • 373
10 votes
2 answers
1k 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 $\...
user avatar
10 votes
2 answers
19k views

Memory complexity?

I am unclear about finding the memory complexity of an algorithm. Some places refer memory complexity as what container would be carrying for instance: ...
Sarp Kaya's user avatar
  • 381
10 votes
1 answer
555 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 ...
Austin Buchanan's user avatar

1
2 3 4 5
30