4
votes
3answers
52 views

Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
2
votes
1answer
45 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
2
votes
2answers
52 views

Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
2
votes
2answers
49 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
1
vote
1answer
44 views

Given a set $S$, find any $N$ numbers than sum to $X$

Similar but different from the problem here. I have an unsorted set $S$ of real numbers, and need to sum elements from $S$ to find the real number $X$; However, It could be from $1$ to $N$ elements ...
0
votes
1answer
35 views

Proving Upper Bound for Two Variable Function?

The question is: Prove (logn)^k = O(n) for every k>=1. I have never encounter a problem for proving an upper bound for two variables, so I am perplexed as to ...
0
votes
1answer
74 views

Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
0
votes
1answer
45 views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that ...
0
votes
3answers
260 views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
0
votes
2answers
135 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
1
vote
1answer
95 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
1
vote
3answers
317 views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
3
votes
4answers
107 views

Algorithm Analysis: How to simplify a summation leading up to a maximal term?

Okay so I have a summation which goes: $$\sum_{i=1}^{n^3} 3i^2\cdot\log(i)$$ My goal is to find the order of the function, not the exact summation amount. I have found the order of it by writing ...
0
votes
0answers
34 views

How to check if a function is negligible?

Let $\epsilon(x)$ be a negligible function. Let $p$ be a polynomial such that $p(k) \geq 0$ for all $k > 0$. What can we say about $\epsilon(p(k))$? Is this a negligible function? If yes, ...
1
vote
1answer
70 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
1
vote
1answer
31 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
0
votes
1answer
428 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
1
vote
1answer
55 views

Suppose $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2)$. Prove $(f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$.

I need to prove that $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2) \implies (f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$ This question is relevant, but I have a slightly different case, so I don't ...
1
vote
1answer
40 views

Proof that $n^2 \not\in \omega(2^n)$

I'm trying to prove that $n^2 \not\in \omega(2^n)$ and I have to do it from definition. $f(n) \in \omega(g(n)) = \left\{f(n)| \forall c>0, c \in \mathbb{R}, \exists n_0 \in \mathbb{N}, \forall n ...
0
votes
1answer
87 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
0answers
103 views

In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?

Take the following insertion sort algorithm: I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
1
vote
1answer
132 views

Is there a function that grows asymptotically faster than the Busy Beaver numbers?

Is there a function that grows asymptotically faster than the Busy Beaver numbers? That is, I know that BB(n)^n grows faster than ...
1
vote
1answer
68 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
3answers
93 views

Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?

Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the ...
1
vote
1answer
113 views

Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
0
votes
1answer
384 views

Is the function $\lceil\lg \lg n\rceil!$ polynomially bounded?

I'm totally lost so please be really explicit in your answers. Thanks for the help. Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, ...
2
votes
3answers
420 views

Polynomial bounds?

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded? Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded? $$\lg = \log_2$$ Polynomially bounded: $f(n)$ is polynomially ...
1
vote
2answers
134 views

Prove asymptotic bound?

Prove: $$n^b = \mathcal{o}(a^n)$$ for and constants $b$ and $a$, where $a > 1$. The book states that: $$\lim_{ n \rightarrow \infty} \frac{n^b}{a^n} = 0$$ The book doesn't prove the limit ...
1
vote
1answer
39 views

Dynamic Programming Trouble, Optimizing time

A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by ...
1
vote
1answer
89 views

Big $\mathcal{O}$ notation for multiple parameters?

The following is an excerpt from CLRS: $\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
0
votes
1answer
37 views

Are these two definition equivalent?

$f(n) = \mathcal{o}(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) \le cg(n), n \ge n_0 $ $f(n) = \pi(g(n))$ if for any constant $c$, there exists ...
2
votes
0answers
92 views

Upper bound for linear function

What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$. $$an + b ...
9
votes
5answers
424 views

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction. I get the intuition behind this question. Clearly, the given function isn’t even growing ...
0
votes
1answer
84 views

What is a basic definition for Big Oh, and it's component parts?

this is a question that somewhat straddles the boundaries of computer science (data structures and ). I'm mostly fine with data structures, until encountering big oh notation.. at which point my head ...
4
votes
3answers
729 views

Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $ where $(f+g)(n) = f(n) + g(n) $ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
1
vote
0answers
83 views

Asymptotic analysis for multiple variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
0
votes
2answers
62 views

Asymptotic constants for a quadratic?

Note than $n$ is a parameter for the functions. For some constants $c_1, c_2$ and $n_0,$$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n > $n_0$. Consider any quadratic function $f(n) =an^2 ...
6
votes
4answers
2k views

Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
-1
votes
4answers
142 views

Is $O(n^2) = O(n^3)$? Prove your answer.

I am not sure how to go about doing this, I know that: $$O(g(n))=\{f : \exists \ c \ \in \Bbb R_+, \ \exists \ n_0 \in \Bbb N, \ \forall \ n\geq n_0 :f(n) \le c·g(n)\},$$ but how do I go about using ...
0
votes
3answers
42 views

Asymptotic analysis of a ratio

Is $ \frac{n^2}{n-2}\in O(n) $ true? Intuitively it seems so but how would I rigorously prove this?
2
votes
2answers
472 views

Big - O estimation

I want to establish a Big-O estimate for the following: $$(n! + 2^{n+3})(111n^3 + 15\log(n^{201} +1))$$ Would the following be correct? $n! = O(n^{n})$ $2^{n+3}=O(2^{n+3})$ $111n^{3}=O(n^{3})$ ...
0
votes
2answers
1k 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
382 views

Prove a bound on matrix multiplication?

Show that $O(\log n)$ matrix multiplications suffice for computing $X^n$. (Hint:Think about computing $X^8$.) $X = \pmatrix{0 & 1 \\ 1 & 1}$ How would I go about doing this? I'm ...
2
votes
1answer
70 views

How does one approach asymptotic relation problems?

Consider the following functions: $f(n) = \frac{n^2}{\log n}$ $g(n) = n(\log n)^2$ Indicate the relation between the two (e.g. $f(n)= O(g)$, $f = Ω(g)$ or $f = Θ(g)$) The above ...
1
vote
1answer
139 views

When can we exchange the order of big/little O and function composition

From Wikipedia Let $f(x)$ and $g(x)$ be two functions defined on some subset of the real numbers. One writes $$ f(x)=O(g(x))\text{ as }x\to\infty\, $$ if and only there exists a ...
3
votes
2answers
921 views

Disproving big O

In the question, we are to assume that f(n) is O(g(n)). Next, we have to decide whether 2^f(n) is O(2^g(n)). According, to some solutions on the internet, this can be proven to be false if we take ...
3
votes
2answers
201 views

asymptotic analysis: what is a basic approach to this?

I am just looking for basic step by step in how to turn a pseudo code algorithm into a function and then how to calculate and show T(n) ∈ O(f(n)), and that T(n)∈ Sigma(f(n)) Also if someone could ...
0
votes
2answers
973 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
4answers
1k views

What is the runtime of a modulus operation

Hi I have an algorithm for which I would like to provide the total runtime: ...
0
votes
1answer
488 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. ...