Questions tagged [analysis-of-algorithms]

Question 1

Goal Prove that $f(n) = a_pn^p + a_{p-1}n^{p-1} + ... + a_1n + a_0$ is $\Theta(n^p)$ Issue I am having trouble proving $f(n)$ is $\Omega(n^p)$. I know I need a $c_0$ and $k$ such that $f(n) \ge c_0n^p$...

Question 2

I know that this has been posted at least once, but the accepted solution doesn't use the substitution method laid out in Introduction to Algorithms by Thomas Cormen. What I've tried so far is this: $...

Question 3

Lets take the function $f(x) = x + (x^2-x)\frac{1+\sin{7x}}{2}$. This function oscillates between $x$ and $x^2$. So it is $O(x^2)$ and $\Omega(x)$ and these are the tightest upper and lower bounds. ...

Question 4

Assume every function is eventually nonnegative. In other words, we are interested in growth rates for measuring time complexity and such. $f = O(g)$ is equivalent to $\limsup \frac{f}{g} < \infty$,...

Question 5

Robert C. Martin in his book "Clean Code" presents an algorithm for finding prime numbers present in Knuth's book. After some cleanup the algorithm looks like the following (in C#): ...

Question 6

How to solve a recurrence relation of this form? $$ a_n = \sum_{i=0}^{n-1} a_{i}a_{n-1-i}(1-\frac{i}{n}), a_0=1 $$ Other information: Because of the symmetric structure inside the summation, it can ...

Question 7

I'm working on the following problem: You have a multiset of $3N$ nonnegative real numbers $S$. You must partition this set into $N$ triples. The goal is to maximize the sum of the products of each ...

Question 8

I'm working on a problem where I need to store $n$ files of sizes $f_1, f_2, \ldots, f_n$ on a hard disk. The disk is divided into segments, each of size ( K ). The problem has the following ...

Question 9

My teacher showed us this recurrence for merge sort, and solved it using guess and check. I don't understand the steps he is taking to simplify and factor the equation. T(n) = 2T(n/2) + n we guess ...

Question 10

I know that, $$a+b=\Theta(\max\{a, b\}).$$ I need to understand the dominating term in this expression, $$\mathcal{O}(m^{\frac{2}{3}}n^{\frac{2}{3}}+m+n).$$ We know that,$$m^{\frac{2}{3}}n^{\frac{2}{...

Question 11

I'm currently studying several classic graph algorithms for shortest paths (Dijkstra, Bellman-Ford, etc.) and came to the following problem: Problem We have $G:=(V,E,\omega)$, a weighted, connected, ...

Question 12

From Rosen's Discrete Math textbook, I feel the part of the proof where they say $$\log_b n = \frac{\log_2 n}{\log_2 b} < \frac{n}{\log_2 b}$$ where $b$ is any positive number not equal to $2$ is ...

Question 13

I know that the question of a closed form for the number of partitions of $n$, often written $p(n)$, is an open one (perhaps answered by the paper referred to in this question's answer, although I'm ...

Question 14

$\text{Consider the following algorithm:}$ ...

Question 15

I want to calculate $\sqrt{a}, a \in \mathbb{R^+}$ with the following algorithm: $y_n = \frac{a}{x_n}$, $x_{n+1} = \frac{y_n+x_n}{2}, n=0,1,\dots,$, with a start value $x_0 \geq \sqrt{a}$. Now there ...

Stack Exchange Network

Questions tagged [analysis-of-algorithms]

Prove Big Theta for degree p polynomial

Is my proof of $T(n) = T(n - 1) + n$ being $O(n^2)$ correct?

Is there a common notation for tightest big-O and big-Omega order?

Is there a characterization of growth rates that are "regularly behaved"?

How does this algorithm for finding prime numbers work? [closed]

How to solve an infinite recurrence relation of this form?

Maximum Sum of Products NP Complete

Why doesn't the greedy heuristic give the optimal solution for file storage?

Explain the steps needed to solve this recurrence by guess and check method

Find the dominating term

Shortest path through vertex in weighted graph (Proof)

Feeling this proof that $\log_b(n)$ is $O(n)$, where b is any positive real number $\neq 2$, has an error.

Is there a closed form method of expressing the content of integer partitions of $n$?

Interpreting an algorithm as an integral

Proving inequality $y_0 \leq \dots \leq y_n \leq y_{n+1} \leq \sqrt{a} \leq \dots \leq x_{n+1} \leq x_n \leq \dots \leq x_n$

Hot Network Questions