Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

1
vote
1answer
38 views

Time complexity of the fast exponentiation method

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} &...
5
votes
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 ...
2
votes
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 ...
2
votes
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 ...
1
vote
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 ...
-1
votes
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?
-1
votes
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 ...
0
votes
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 ...
1
vote
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 ...
-1
votes
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(...
0
votes
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 ...
0
votes
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: ...
1
vote
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, ...
5
votes
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}!...
3
votes
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 \...
1
vote
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 ...
1
vote
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)...
0
votes
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. ...
-2
votes
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. ...
3
votes
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}$ ...
1
vote
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. ...
5
votes
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,...
4
votes
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(...
4
votes
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 ...
3
votes
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)$ ...
0
votes
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 ...
3
votes
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 ...
3
votes
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)...
3
votes
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$. ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
-1
votes
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 ...
1
vote
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 ...
1
vote
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 ...
3
votes
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 ...
3
votes
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 ...
1
vote
1answer
63 views
2
votes
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?
-2
votes
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(...
-2
votes
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 ...
1
vote
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?
4
votes
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)$ ...
3
votes
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 ?
1
vote
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), ...
4
votes
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 ...
1
vote
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 } ...
0
votes
2answers
41 views

Big-O Justification Question

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 ...