Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
2answers
524 views

Algorithm analysis question in growth of functions

How would I solve the following. An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500? Can anyone help me ...
3
votes
1answer
3k views

Big O notation of max?

I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that ...
28
votes
1answer
915 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 ...
1
vote
1answer
107 views

Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
2
votes
1answer
94 views

Does $O(1) * o(1)$ equal a $o(1)$ function?

Say I have two functions $f(x) = O(1)$ and $g(x) = o(1)$. Let $h(x) = f(x)g(x)$. Is $h(x) = o(1)$? By definition of small-o $g(x)$ must approach 0 as $x \rightarrow \infty$, so I think yes. However, ...
4
votes
1answer
2k views

Algorithms with polynomial time complexity of higher order

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting. Linear Search - with time complexity $O(n)$ Matrix Addition - with time complexity $O(n^...
8
votes
1answer
111k views

Complexities of basic operations of searching and sorting algorithms [closed]

Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is ...
5
votes
1answer
2k views

Finding recurrence when Master Theorem fails

Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer. $T(n)= 4T(n/2) + \frac{n^2}{\lg n}$ In above ...
4
votes
1answer
3k views

Time complexity based on two variables

Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant $c$. ...
2
votes
1answer
1k views

Decreasing runs of inner loop in outer loop [duplicate]

I am trying to determine the worst case runtime of this program: while n > 1 for i = 1,..,n m = log(n) n = n/2 Obviously the outer loop runs ...
4
votes
5answers
6k views

Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?

The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$. $O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
4
votes
2answers
2k views

Asymptotic Properties of Functions in Complexity Analysis

When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and ...
0
votes
1answer
63 views

Show that a function belongs to grade of incline [duplicate]

This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$ I need to ...
19
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)$.
6
votes
2answers
331 views

Landau Notation, Definitions: Limits vs. Corman's

When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.: $$o(g(n))=\{ f(n): \forall c>0:\exists n_0>0:\; 0\leq f(n) < cg(n)...
3
votes
2answers
1k views

Methods for Finding Asymptotic Lower Bounds

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for ...
10
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 ...
-2
votes
1answer
6k views

Complexity of a while loop that divides by parameter by three each iteration

I've learned that a while loop such as int i = 100; while (i >= 1){ ... ///Stuff i = i/2 } will run in logarithmic time, specifically, ...
2
votes
2answers
424 views

Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
7
votes
2answers
302 views

Are functions in O(n) that are nor in o(n) all in Θ(n)?

One of my lectures makes the following statement: $$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$ Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ ...
6
votes
1answer
133 views

Asymptotics of a function that decreases as n increases

A homework assignment asks me to state the complexity in Big-O notation of the function $$f(n) = 7n – 3n \log n + 100000 $$ I graphed this function and decreases all the way down to zero nearly its ...
4
votes
3answers
656 views

Why is $n \log \log n$ not tightly bounded by $n$?

I don't understand why $n \log \log n $ is not $\Theta (n)$. Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n ...
5
votes
3answers
8k views

Solving $T(n)=4T(n/2)+n^2$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T(n/2)+n^2$$ My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master ...
1
vote
1answer
754 views

Solve a recurrence by drawing the recursion tree?

I'm studying for an entrance exam and I have sample questions. One of the questions is this Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$ has a solution $T(n) = \omega(n \log n)$. ...
9
votes
2answers
883 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 ...
20
votes
7answers
3k 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 ...
4
votes
4answers
7k views

Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up). Why does ...
5
votes
3answers
279 views

Why is $(\log(n))^{99} = o(n^{\frac{1}{99}})$

I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero. $$ \lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}} $$ But I'...
2
votes
2answers
1k views

Running time of a nested loop with $\sum i \log i$ term

So I have the following pseudo-code: Function(n): for (i = 4 to n^2): for (j = 5 to floor(3ilog(i))): // Some math that executes in constant time So ...
20
votes
1answer
720 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 ...
25
votes
5answers
11k 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" (...
12
votes
2answers
469 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 ...
3
votes
2answers
2k views

How to the examples for using the master theorem in Cormen work?

I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples $3T( \frac{n}{4} ) + n\log(n)$ $2T( \frac{n}{2} ) + n\log(n)$ ...
2
votes
1answer
243 views

asymptotic notations with two exponents

I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these ...
0
votes
1answer
163 views

Explanation of a specific recurrence with respect to Master Theorem

Concerning the Master Theorem. I have found the following equation as the base of analysis: $\quad T(n) = aT(n/b) + \Theta(n^k)$ but I also found the following: $\quad T(n) = aT(n/b) + \Theta(...
2
votes
1answer
2k views

Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity. Can it ...
3
votes
1answer
108 views

Showing bounds of a recurrence

I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that: The solution of $T(n) = 2T(\...
1
vote
1answer
80 views

How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
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$ ...
3
votes
5answers
806 views

What does big O mean as a term of an approximation ratio?

I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem. The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$. ...
4
votes
1answer
166 views

What can be said about Θ-classes in m and n if we know that m < n?

A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it is $\Theta(n^2\log n)$?
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 ...
2
votes
1answer
215 views

Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

The following is an excerpt from CLRS: The definition of $g(n)$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is ...
3
votes
2answers
540 views

If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?

The following is an excerpt from CLRS: $\Theta(g(n))= \{ f(n) \mid \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$. Assuming $n \in \...
2
votes
1answer
265 views

Input to make worst case on big O not possible?

Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a ...
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?
4
votes
1answer
120 views

Height of AVL after entries

Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height? My idea: the height of an AVL tree is ...
0
votes
3answers
146 views

How to guess the value of $j$ at the end of the loop?

for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ; All variables are integers.(i.e. if decimal values occur, consider their floor value) Let $\text{val}(...
7
votes
2answers
159 views

Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem For instance, the Arora-Barak book ...
1
vote
1answer
4k views

Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ [duplicate]

Possible Duplicate: Solving or approximating recurrence relations for sequences of numbers I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$ But how do you get to ...