Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

-2
votes
1answer
18 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. ...
-1
votes
0answers
18 views

prove that 2.n3 + 3.n + 10  O (n4) [duplicate]

plz provide the answer of below question prove that 2.n3 + 3.n + 10  O (n4)
3
votes
4answers
615 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
votes
0answers
20 views

Runtime complexity for selection sort using recursion [duplicate]

I have implemented selection sort using recursion for which I am getting following function for var inputArr = [99,88,77,66,55,44,33,22,11,10]; $(-1 + (-1)^n + 8 n ...
1
vote
1answer
68 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
71 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 ...
4
votes
2answers
254 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 ...
4
votes
1answer
58 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
85 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
43 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
101 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) ...
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
57 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
205 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
20 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
60 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
515 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
59 views
2
votes
1answer
79 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
53 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 ...
-2
votes
1answer
29 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
278 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
68 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
76 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
84 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
39 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
70 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
40 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 ...
6
votes
4answers
249 views

Big Oh vs Big Theta

I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n_0$ s.t. $f(n) \leq cg(n) \forall n \geq n_0$. Similarly, $f(n) \in ...
1
vote
2answers
463 views

“Not in big theta but in big O”

Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me to prove that ...
1
vote
1answer
21 views

What are witnesses C and k for an O-bound?

Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.) Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the ...
2
votes
1answer
31 views

Quicksort $T(n)_{best}=\Omega(n\log n) $ proof

About the proof that quicksort has $T(n)_{best}=\Omega(n\log n)$. I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't ...
1
vote
2answers
82 views

What is the Big Theta of $(\log n)^2-9\log n+7$?

How can I find the Big Theta of $(\log n)^2-9\log n+7$? I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
0
votes
0answers
6 views

How can I arrive at an asymptotically tight upper bound and prove its correctness? [duplicate]

I am aware of Big-Oh, but often times my bounds are sloppy, which while correct is not tight enough. How can I ensure that my bound is tight? Is there a way to prove or mathematically arrive at an ...
2
votes
2answers
98 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 ...
3
votes
2answers
134 views

Algorithm for finding a mouse hole in a wall in O(n) time

There is this question: As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you ...
0
votes
0answers
55 views

What is the big-O and big-$\Omega$ of this function? [duplicate]

The function is given below. $\displaystyle \frac{1}{\sqrt{n!}} \left( m_t \left(N_t!\right)^{m_t} \right)^t . 2^{\frac{5n + 2t}{2}} \left( \sqrt{n}\right)^{\frac{n}{2}}$ Here, $n$, $m_t$, $N_t$ are ...
0
votes
1answer
205 views

Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n)) [duplicate]

I have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? ...
0
votes
0answers
7 views

How to prove this asympotic notation [duplicate]

How can I prove that this asympotic notation is correct or not? (〖7∙n)〗^9=ϑ((〖7+n)〗^9
0
votes
1answer
47 views

Differentiating between BubbleSort and InsertionSort

This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this. The problem is this: You have two unknown sorting algorithms, one is Bubble Sort, the ...
3
votes
1answer
50 views

Why add a +1 to the constant proving an O(n) bound?

I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$. To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$, we take $\qquad\displaystyle \lim_{n \to ...
6
votes
2answers
99 views

Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the “+1” part?

I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain ...
-1
votes
1answer
74 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
1
vote
2answers
184 views

Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...