Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

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

What are the Correct Conditions for Akra-Bazzi Master Theorem? (Cross-Post) [on hold]

NOTE: this question is cross-posted see original here: http://math.stackexchange.com/q/1767062/327486 Computational Science: http://scicomp.stackexchange.com/q/23888/20247 I deleted this post for ...
0
votes
1answer
39 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
54 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
197 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
19 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
20 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
58 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
491 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 ...
-3
votes
0answers
44 views

Solution of $T(n) = T(n/3) + 1$ [duplicate]

A recursive algorithm's time to solve a problem of size $n$ is represented by the following recurrence equation: $$ T(n) = T(n/3) + f(n), \text{where $f(n) = 1$}. $$ What is the rate of growth of ...
-1
votes
0answers
38 views

Function is not Big O of another Function [duplicate]

If I want to show that $$ f(n) \in O(g(n)) $$ I know I have to prove $$ f(n) \le c * g(n) , \exists c > 0, \exists n_0 \in \mathbb{N}, \forall n \gt n_0 $$ If I want to show $$ f(n) \notin ...
1
vote
1answer
54 views
2
votes
1answer
77 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
52 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
26 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
277 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?
3
votes
1answer
48 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
75 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
83 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
37 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
62 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
39 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
232 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
450 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
30 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
75 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
87 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
129 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
183 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
46 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
48 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
98 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
72 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
178 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 ...
0
votes
1answer
60 views

If f(n) = Ω(n) and g(n) = O(f(n)), what do we know about g?

Let f(n) = Ω(n), and g(n) = O(f(n)).Then g(n) = _______. I thought of it this way, since f(n) is Ω(n),then f(n) belongs to the set of functions defined by Ω(n), ie,{n,$n^2$,$n^3$ ....}. So g(n) ...
1
vote
1answer
42 views

Number of levels in the recursion tree

While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a ...
4
votes
1answer
31 views

How to solve for p in Akra-Bazzi method for analyzing time complexity?

Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and ...
53
votes
10answers
5k 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 ...
2
votes
0answers
90 views

Why do we focus on asymptotics when analyzing algorithms? [duplicate]

Maybe a newbie question, but why when we analyze algorithms do we focus on asymptotics? It seems to me the performance of algorithms on finite input sizes (after all, problems are rarely infinitely ...
0
votes
0answers
18 views

How to prove log^b n = o(n^a) [duplicate]

I'm trying to prove $$log^b n = o(n^a)$$ Method of Induction Base Case: Holds n =1 ...
0
votes
0answers
22 views

Joining k 2-3 trees

I was given the following question, and would like your help with it: Let $T_1, T_2, T_3, ..., T_k$ be a collection of k 2-3 trees. The height of tree $T_i$ is marked $h_i$. Assumptions: 1) every key ...
4
votes
2answers
96 views

Is Ω(f+g) = Ω(min(f,g))?

We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$. So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$? Then what is $\Theta(f(n)+g(n))$ equal to?
0
votes
1answer
16 views

Computer science asymptotic terminology

I have been hearing the phrases quasipolynomial, superpolynomial and subexponential. I think know what quasipolynomial and subexponential is. I believe these are functions respectively of form ...
7
votes
1answer
393 views

Big-O proof for a recurrence relation?

This question is fairly specific in the manner of steps taken to solve the problem. Given $T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$. So the steps were as follows. We want to prove that $T(n) ...