Tagged Questions
0
votes
0answers
15 views
Asymptotic recurrences?
$$T(n) = 2T(n/2) + \Theta(n), n > 1$$
$$T(n) = \Theta (1), n \le 1$$
$$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n > 1$$
$$G(n) = \Theta (1), n \le 1$$
Prove $T(n)$ ...
1
vote
1answer
47 views
Why is it okay to do this?
I am studying asymptotic recurrences for algorithms, and the book says:
$$T(n) = 2T(n/2) + \Theta (n)$$
is technically
$$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$
for an ...
1
vote
0answers
15 views
Prove or disprove asymptotic relation of two sets
I am looking for a while to prove or disprove: (preparing for finals)
O(f(n)-g(n)) ⊂ |O(f(n)) - O(g(n))|
where || is absolute value. Note that ⊂ is needed and not ⊆
I assumed the a subtraction ...
1
vote
4answers
98 views
Error in “proof” of $n^2 \in O(n)$.
I need some help. I have homework:
I need to disprove that $f(n^2)$ belongs to $O(n)$.
Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
3
votes
1answer
48 views
Subtraction of Big $O$'s
So we were asked to prove something in class, but I can't understand the following expression:
What is $O(n^2)-O(n^2)$?
I understand big O notation, but what I don't understand is the ...
0
votes
1answer
55 views
Big-O Big theta Big omega papers
I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
2
votes
3answers
129 views
What does O(n+k) mean verbally
I wonder the english explanation of O(n+k). Does it mean, the algorithm will run at most n+k times? Or does it mean the algorithm will run at most n or k times? And also is it same with O(n)+O(k)?
...
1
vote
1answer
46 views
What does it mean for a function to be polynomially bounded
There is a definition in my notes and says,
When functions are polynomially bounded, the initial conditions (the value on
small inputs) do not make a difference for the solution in ...
2
votes
1answer
45 views
How can I prove big-oh relation between $\log_2(\log_2 n)$ and $\sqrt{\log_2 n}$
How can I prove big-O relation between $f=\log_2(\log_2 n)$ and $g=\sqrt{\log_2 n}\,$?
I want to find the constants, $c, N$ such that $\ g(x) \leq cf(x)$ for all $x>N$.
0
votes
1answer
72 views
Big O notation doubt f(n) = g(n)
If $$f(n) = g(n) = n $$
then Is $$f(n) = O(g(n)) $$
As far as I know it is according to the definition of Big-O notation. So, if this is the precondition then Is
$$2^{f(n)} = O(2^{g(n)})$$
?
I ...
1
vote
2answers
32 views
The growth rate of the functions with respect to each other
There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$?
Thank you.
1
vote
0answers
42 views
Asymptotic notation of the following function
I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated.
a) ...
3
votes
1answer
22 views
Indicating the complexity of functions
I am not sure about my answer about the following question. Can anyone help?
I try to express whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$, where $f(n)=n^{0,1234}$ and ...
1
vote
1answer
74 views
Rate of growth of exponential functions
I have difficulties about proving the following:
Prove that exponential functions $a^n$ have different orders of growth for different
values of base $a>0$.
It looks obvious that when $a=3$ it ...
1
vote
2answers
120 views
Deciding whether a function is O(n), Ω(n), or Θ(n)
First of all, this is my homework question, i have my answers and i want to be sure whether i am missing something. I have difficulties about deciding whether f(n) is O(g(n)), Ω(g(n)), or Θ(g(n)):
...
2
votes
3answers
54 views
Understanding $O$-notation and the meaning of $\Omega$
I am studying algorithms, and I have problems on the concepts from an exercise. Thank you so much!
Which of the following equations lie in $O(n)$, $\Omega(n)$, $\Theta(n)$ and why.
a. ...
1
vote
2answers
38 views
Θ(n) + O(n) = ? (recurrence equation)
If I have a recurrence equation like:
T(n) <= T(n/2) + Θ(n) + O(n)
Is the above expression equal to:
T(n) <= T(n/2) + Θ(n)
Or is that expression equal to:
T(n) <= T(n/2) + ...
0
votes
1answer
161 views
Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$
Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.
Here's what I've come up with, but I'm not ...
0
votes
0answers
44 views
Solving the recurrences of algorithms
Im having some trouble understanding recurrences.
I have an assignment where I have to solve some recurrences, theyre generally in the form of:
$$T(n) = aT(n/b) + f(n)$$
I have 3 general formulas ...
3
votes
1answer
74 views
BigO sorting complexity help
Given a bit sequence of length a, what is the minimum number of comparisons needed to determine if it contains a pair of consecutive 1's in BigO notation
2
votes
1answer
100 views
Lower bound for matrix sorting?
Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.
I found that it is $O(n^2logn)$ by just ...
0
votes
1answer
48 views
Proof for asymptotic tight bound when $C=a_k/2$
In an algorithms lecture in school theres a proof for asymptotic tight bound like:
Take $C=a_k/2$ and show that $f(n) \ge \frac{a_k}{2} n^k$ when $n > N$
for some $N$.
$$\begin{align} ...
1
vote
1answer
56 views
Help finding Complexity in Big-O notation
I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
0
votes
1answer
162 views
Dominant term and Big Omega
For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation.
$$n^3+n^2\log_2(n)+n^3\log_2(n)$$
So, I ...
0
votes
1answer
38 views
Asymptotic Complexity Problems with Subtraction
I know that when finding the asymptotic complexity of a given function, you must pay attention to the rate of change in a for loop. For example:
for (i = 1 to n)
{
//some action of constant time ...
1
vote
1answer
48 views
Big 0h question how are they similar?
How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
0
votes
1answer
89 views
Is this why this summation is equivalent to this Theta notation?
So I'm not sure if I misunderstood the lesson or not.
$$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2) $$
Are these equivalent because:
$$ \sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = ...
1
vote
1answer
89 views
Show that $(n + a)^{b}$ = $\Theta(n^{b})$
In the book I'm following I got the following solution:
To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 ...
0
votes
1answer
405 views
How to prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$?
Using the basic definition of theta notation prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$
I came across two answer to this question on this website but the answers weren't clear to me. ...
2
votes
1answer
83 views
Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?
If we have an algorithm with complexity $\Theta(m + n^2)$ and we know that $0 < m < n^2$ then its complexity becomes $\Theta(n^2)$. But if we had an algorithm with complexity $\Theta(m\log{n})$ ...
0
votes
1answer
62 views
Formula for determining size at which one growth rate beats another?
My apologies if the title of the post is a bit confusing...wasn't sure how to word the problem.
I ran across some questions in the form of:
Suppose we are comparing implementations of insertion ...
0
votes
0answers
118 views
Solve recursion formula using Recursion Tree concept
I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea.
I will first write down the exercise and then I'll try to explain ...
1
vote
3answers
91 views
Order of magnitudes comparasions
I have a list of order of magnitudes I want to compare.
My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation.
I need your help with the following.
I ...
0
votes
3answers
58 views
Big-O compared to a new Operator
I'm trying to figure out a new operator compared to the Big O.
Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
0
votes
2answers
379 views
Big O Notation and finding witnesses
I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really ...
2
votes
1answer
81 views
big O notation with asymptotically nonnegative increasing functions
Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show:
$f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh.
I can't quite figure this out, can ...
0
votes
2answers
135 views
Resolve this recurrence: $T(2^n) = T(2^{n-1}) + 2^n$
I need to resolve this recurrence:
$$T(2^n) = T(2^{n-1}) + 2^n$$
The conditions are:
Give a $\theta$ bound.
In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ...
1
vote
1answer
281 views
Sum of series with log in each term
I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i)
$$
T(n) = T(n-2) + \frac{1}{lg \; n}
$$
I tried few ways, like ...
1
vote
1answer
75 views
Big-Oh of $\log (n^x)$
Prove that if $d(n) = \log(n^x)$, where $x$ is a constant greater than zero, then $d(n)$ is $O(\log(n))$.
I have attempted this solution but it seems to me that $\log(a) > \log(b$) if $a > b ...
1
vote
2answers
1k views
$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem
Assume that
$$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$
By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
2
votes
1answer
78 views
What is the value of this summation in Big O terms?
I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below:
$$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$
What will be the Big O ...
3
votes
1answer
80 views
matrix “flag” clearing
I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example:
$$
...
1
vote
1answer
224 views
What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?
So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
0
votes
3answers
676 views
Master theorem solving
I'm starting to study the master theorem, why does something like
$$T(n) = aT(n/b)+f(n)$$
solves to
$$f(n)^{\log_ba}$$ ?
I'm a bit confused on the resolution
0
votes
1answer
40 views
Estimates of Gaussian Logarithms
I've been implementing logarithmic number system and I came across these functions called Gaussian logarithms:
$f(x) = \log(1 + e^x)$.
$g(x) = \log(e^x - 1)$ for $x > 0$.
$h(x) = \log(1 - e^x)$ ...
1
vote
3answers
447 views
What does asymptotically optimal mean for an algorithm?
What does it mean to say that
heap sort and merge sort are asymptotically optimal comparison sorts .
I know What the Big O , Big Omega($\omega)$ and Theta($\theta$) notations are and I also know ...
0
votes
3answers
1k views
Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg n)$
I'm trying to solve the recurrence relation:
$$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$
My first step was to let $m = \lg n$, making the above:
$$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$
If ...
0
votes
1answer
327 views
Improving Gift Wrapping Algorithm
I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points.
...
3
votes
0answers
142 views
When do floors and ceilings matter while solving recurrences?
I came across places where floors and ceilings are neglected while solving recurrences.
Example from CLRS (chapter 4, pg.83) where floor is neglected:
Here (pg.2, exercise 4.1–1) is an example ...
4
votes
2answers
239 views
Abuse of big-O notation? (version 2 - simplified and revised)
Given exam question:
Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and
$g(n)=1+0.1n^2$ respectively.
By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable
...
