Tagged Questions

Questions about asymptotic notations and analysis

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &... 3answers 79 views Solving recurrence relation T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n using method of guessing and confirm? The book I am following explains the solution as, As we can see,the size of sub problems at the first level of recursion is n.So, let us guess that T(n)=O(n\log n) and try to prove that our ... 1answer 26 views Big Theta for finding combinations of arbitrarily sized subsets from n total elements Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset? Assume the elements ... 3answers 205 views Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n The questions is to find the running time T(n) of the following function:$$T(n)=3\cdot T(n/2) + n \tag{1}$$I know how to solve it using Master theorem for Divide and Conquer but I am trying to ... 1answer 34 views How do I find running time for the following divide and conquer problem? Question is to find the runtime T(n) of following problem by solving the recurrence. T(n)=16\cdot T(\frac{n}{4}) + n!. I went through the following theory. If the recurrence relation is of the ... 0answers 8 views What is the set of possible set of values of c for which A1 is polynomial time algorithm? [closed] Let algorithm A1 have worst case running time T(n) = O(XX). Let X = (log n)c. What is the set of possible set of values of c for which A1 is polynomial time algorithm? 0answers 26 views How do I prove or disprove that n^3 - 5n \log{n} = \theta(n^3)? [duplicate] I learn computer science in university and I was given this question in my data structures course test, so the question was to prove or disprove n^3 - 5n \log{n} = \theta(n^3). I disproved it by ... 2answers 51 views 𝑇(𝑛) = 𝑇(𝑛 − 2) + 4, giving asymptotic bounds [duplicate] How do I go about solving this? When I try to google examples I only see problems with "+1" or "+n" constants and never anything above that. If possible could anyone also describe the suggest method ... 1answer 49 views Dijkstra's algorithm runtime for dense graphs The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is O((E+V)\log V). For a dense graph such as a complete graph, there can be V(V-1)/2 edges. Since E \sim ... 1answer 26 views Converting pseudo code to a recurrence relation equation? [duplicate] The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(... 0answers 9 views Difference between the definitions regarding distribution of prime numbers [migrated] Following are the two theorems that Hardy and Wright state in their book Theorem A: The number of primes not exceeding x is given by \pi(x) \sim \frac{x}{\log{x}}. Theorem B: The order ... 0answers 20 views What are some quadratic run time tasks (algorithms)? [duplicate] Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist). EDIT: ... 2answers 88 views big-O and Θ notation subset I was reading “Introduction to Algorithms” by CLRS and it says Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, ... 3answers 115 views Is \Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}}) correct? I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063: ...and therefore the running time is \Omega(m!)=\Omega(\sqrt{n}!... 4answers 214 views Landau Notation: Why is O(f) (not) the set all g < c*f? I am somewhat confused here about the Landau notations. Let's say we are dealing with function from \mathbb{N} to \mathbb{R}. Then we can define \mathcal{O}(f) = \left\{ g : \mathbb{N} \to \... 2answers 37 views Why should small o notation has to satisfy the equation for all values of the constant Big-O of a function i.e. f(n) = O(g(n)) is such that both c and \textbf{n}_0 can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the ... 1answer 46 views In which O-class does my Θ-result belong? In a multiple-choice test, I'm asked to solve the recurrence T(n)=2T(n/2)+n/2. I've done this using the master theorem: f(n)=n/2, a=2, b=2, so we're in the second case and T(n)=\Theta(n\log n)... 1answer 44 views Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)? This is the algorithm I'm using: http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627 Specifically C#, but the linked thread has numerous languages. ... 1answer 25 views How can time complexities be elements of others? [duplicate] I have a problem that I solved, but I'm unsure if my answers are correct or not. I've never seen the implementation of time complexities as elements of others. ... 6answers 786 views Is there a meaningful difference between O(1) and O(\log n)? A computer can only process numbers smaller than say 2^{64} in a single operation, so even an O(1) algorithm only takes constant time if n<2^{64}. If I somehow had an array of 2^{1000} ... 1answer 72 views Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation) I am currently learning landau notations and am stuck on the following True/False question. What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. ... 2answers 77 views Big-O and not little-o implies theta? If f(n) is in O(g(n)) but not in o(g(n)), is it true that f(n) is in \Theta(g(n))? Similarly, f(n) is \Omega(g(n)) but not in \omega(g(n)) implies f(n) is in \Theta(g(n))? If not,... 2answers 268 views Is \log(n!) in \Theta(n \log(n))? I had two questions on my automated test which I don't understand the answer for. \log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1). So it is in O(n\log(... 1answer 75 views Complexity of division The article Computational complexity of mathematical operations mentions that the complexity of division in O(M(n)), and that "M(n) below stands in for the complexity of the chosen multiplication ... 2answers 92 views Why do we use big O rather than \Omega when discussing best case runtime? When discussing the worst case runtime T(n) of an algorithm, we attempt to bound T(n) above by some simple function g(n), so that T(n) = O(g(n)). When discussing the best case runtime T(n) ... 0answers 44 views Calculating Big-O I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine)  The ... 1answer 117 views What is the fastest addition algorithm on a turing machine? What's the asymptotic running time of the fastest algorithm for adding two n-digit decimal numbers on a Turing machine? To specify, the input is of the form a_1+a_2 where a_1 and a_2 are ... 2answers 37 views Arithmetic of asymptotic functions I faced some problem that involves arithmetic over asymptotic functions. These are as follows: Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is: (a) Ω(n) (b) O(n)... 1answer 30 views Solving recurrence relation when cost of all combining steps is constrained I have a recurrence relation T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n), where each  0 < d_i < 1, f(x) > 0 for all \, x > 0 and f(xy)=f(x) \cdot f(y) for x,y\geq 0. ... 1answer 27 views Comparing asymptotic complexity of functions \log{n}, (\log{n})^c and \sqrt{n} [duplicate] I usually follow approach of taking logs and putting arbitrary large powers of 2 for n and reducing the given function to some constant value for large value of n. So in this case I did it as ... 1answer 40 views Are all problems approached and solved in fundamentally the same way? This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot. This questions stems from a conversation a friend and I were having ... 1answer 60 views How to express time complexity when the exponential “e” comes into play? [duplicate] I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size. While timing the execution of ... 4answers 211 views Complexity analysis of an unsolvable algorithmic problem? In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned ... 1answer 21 views Big O Running Time Analysis What is the big O running time for following method() by counting the approximate number operation it performs. How can I identify the running time of each line? I ... 0answers 22 views Can anyone give an example for worst case of quick sort if we employ median of three pivot selection? If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also ... 2answers 61 views Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve ... 1answer 30 views Replacing n with 2n in asymptotic bounds I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem 6 of the paper on page 632, the authors go on ... 2answers 519 views Why does the square root of n! grow exponentially faster than exponential functions? I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem 6 of the paper on page 632, the authors go on ... 0answers 17 views Find an asymptotically tight bound (big-theta) for the runtime of the following algorithm? [duplicate] ... 1answer 63 views What is an upper bound of T(n) = 2 T(3n/10) + T(4n/10) + n ... 1answer 80 views Why is (small) o(n^2) \neq n^2? [duplicate] We know that 10n^2 = O(n^2) but 10n^2 \neq o(n^2). What is the underlying principle? 3answers 54 views Big O relationship between n^{10\log n} and (\log n)^n [duplicate] I need help with a home task with computer science. the problem is: compare the two complexity functions: F(n) = n^{10\log n} and G(n) = (\log n)^n. Which is O(\ ) of the other? Which is \Omega(... 1answer 31 views Complexity for minimum subset sum of size n-k Disclaimer: Not a HW. Given n sorted positive floating point numbers, and one has to find the minimum subset sum of size n-k. What would be the most efficient way? I can figure out using Brute ... 3answers 283 views Can I simplify log(n+1) before showing that it is in O(log n)? Had a question about the following:$$\log (n+1) \in O(\log n)$$Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold? 1answer 86 views Analysing a small recursive algorithm I need to calculate the complexity of func5, depending on variables n, m. func4 is a function whose complexity is \Theta(n+m) ... 2answers 77 views how to prove that nlogn is not Θ(n) without using limits? i'm studying an algorithms designing and analysis , and i've question about Big-theta how can i prove that nlogn is not Θ(n) without using limits ? 1answer 85 views Big Omega of a while loop I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is Ω(1), ... 1answer 40 views Confusion with analysis of hashing with chaining I was attending a class on analysis of hash tables implemented using chaining, and the professor said that: In a hash table in which collisions are resolved by chaining, an search (successful or ... 2answers 78 views Big-O and little-o notation I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following:$$O(n^c) = o(n^k) \text{ for } ...
I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so ...