Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

0
votes
1answer
32 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
52 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
104 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 ...
-1
votes
0answers
16 views

What is wrong with the below complexity analysis of Universal Turing Machine's simulation? [closed]

In Arora Barak at page no. 32 it says that once we perform the shift with $i$ index, the next $2^i - 1$ shifts of that particular tape will have all index less tha $i$. Since in total there can be $T$ ...
0
votes
0answers
53 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
76 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
39 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
43 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 ...
5
votes
3answers
89 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
64 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
151 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
55 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
36 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
19 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 ...
48
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
21 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
87 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 ...
8
votes
1answer
376 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) ...
1
vote
1answer
14 views

What set of primitive operations are assumed to be constant time in complexity analyses?

Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both ...
1
vote
1answer
72 views

Is O(ln n) “exponentially faster” than O(n)?

I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear ...
0
votes
3answers
81 views

Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$?

How to find which of $2^{n}$ to $n^{a}$ is an (upper bound, tight bound asymptotically larger, etc..)? I tried to use the formula: $$ \lim_{n\to\infty} \frac{f(n)}{g(n)} $$ where $f(n) = n^{a}$ and ...
0
votes
1answer
46 views

Comparing asymptotic notations [closed]

I have a problem P that is said to be O(n^7) in the worst case. I'm asked to agree or not if it is solvable in O(n^9) time. And also I'm asked to agree or not if P cannot be solved faster than Ω(n^7) ...
1
vote
1answer
19 views

Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$. ...
4
votes
1answer
57 views

How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

I am basically trying to solve the following question: Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set. At each step, sets can ...
0
votes
1answer
42 views

How to prove that a polynomial of degree n is θ(x^n) [duplicate]

How can I prove that if $T(x)$ is a polynomial of degree $n$ then $T(x) = \Theta(x^n)$.
2
votes
0answers
120 views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
3
votes
4answers
170 views
0
votes
1answer
43 views

Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

I'm trying to figure out if: $\log^2n = O(n)$ and $ n = O(\log^2n)$ are true or if one or both are false. So far I've concluded that both are false because if $n = 8$ for the first one, then ...
0
votes
0answers
42 views

What is the difference between O(n^2) and O(N)[N*O(1)]?

I was reading this article on gperf. In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
2
votes
1answer
52 views

Master method recurrence question [duplicate]

This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below). For a recurrence of $$T(n) = a T(\frac{n}{b}) ...
0
votes
0answers
33 views

Time Complexity when loop variable depend upon outer loop variable [duplicate]

What is the time complexity of the following piece of code in worst case? ...
9
votes
4answers
277 views

What does $\log^{O(1)}n$ mean?

What does $\log^{O(1)}n$ mean? I am aware of big-O notation, but this notation makes no sense to me. I can't find anything about it either, because there is no way a search engine interprets this ...
1
vote
0answers
33 views

Efficiently comparing total values of two unsorted arrays [closed]

The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater? Would be as simple as prefix sum ($O(n)$) for ...
5
votes
2answers
209 views

Is log n! = Θ(n log n)? [duplicate]

Why is $\log(n!)=\Theta(n\log n)$? I tried: $\log(n!) = \log1 + \dots + \log n \leq n \log n \Rightarrow \log(n!) = O(n \log n)$. But how can we prove $\log(n!) = \Omega(n \log n)$ without ...
1
vote
0answers
47 views

Algorithm to find min pos difference between two integers in an array

The question I'm faced with: Let $A[1], A[2], ...,A[n]$ be an array containing $n$ very large positive integers. Describe an efficient algorithm to find the minimum positive difference ...
2
votes
1answer
78 views

Adding orders of growth

I am confused as to how this is true: O(n log n) + mO(log n) = O((m + n) log n) I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log ...
0
votes
1answer
29 views

Big O Proof for Logarithmic Function [duplicate]

I am an undergraduate student in Computer Engineering and going through one of the textbook examples, I am asked to prove that $T(n)$ is $O(\log{}n)$ Where $T(n)= 5\log_{2} 2n +7$. I understand ...
1
vote
1answer
52 views

Calculating execution time for recursive algorithm [duplicate]

How would I calculate the execution time, T(n), for this algorithm? ...
-2
votes
1answer
144 views

Does ln n ∈ Θ(log2 n)? [duplicate]

Is that statement false or true? I believe it's false because ln(n) = log base e of n. So therefore, log base 2 of n can be a minimum because in 2^x = n, x will always be less than y in e^y = n. ...
3
votes
1answer
101 views

Big-O Notation Statement True? [duplicate]

Considering functions f and g, is the following true? $ (f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$ If not, can you please state an example? Despite thinking hard, i could not find ...
2
votes
0answers
34 views

Big O Notation Simplification [duplicate]

So I'm trying to learn how to simplify Big O notations, these are the ones i'm working on (also sorry if i mess up the format, i'm new) So the first one i have is: f(n) = n g(n) = n/loglog 12 I ...
3
votes
1answer
41 views

What's the formal definition of Big-O notation for functions of more than one variable?

For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$. What I ...
0
votes
1answer
29 views

Selection algorithm variant for an array

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with. Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys. ...
2
votes
1answer
24 views

Understanding multi-variable big O (time complexity)

I have something of this kind: $$(n-1) d m + m + 2m*v+2v^2 + v$$ Where all n,d,m,v are variables. My little knowledge of computational complexity leads to do this kind of approximation: $$ O( ...
3
votes
3answers
164 views

Confused about proof that $\log(n!) = \Theta(n \log n)$

So I was able to show that: $\log(n!) = O(n\log n)$ without any problems. My question is when trying to prove that $\log (n!) = \Omega(n\log n)$. I was able to show that: $$\begin{align*} \log n! ...