# Tagged Questions

4answers
57 views

### How to prove correctness of this algorithm

Situation There is a long patch of grass with seeds planted along it. Each seed needs to be within 2 metres of a sprinkler in order to be watered daily. Describe an algorithm that will result in ...
3answers
25 views

0answers
600 views

### proving a greedy algorithm with a exchange argument

I have the following problem: We have a set of tasks that requires some preprocessing time. When the job is preprocessed, the job can be executed on a parallel thread that also requires some time. ...
3answers
337 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 deﬁnition of big-oh. I can't quite figure this out, can ...
3answers
525 views

### Proving a factorial is not a certain complexity

I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that? Problem: Prove ...
2answers
1k views

### Calculating Average Case Complexity

I am trying to find the average case complexity of a sequential search. I know that the value is calculated as follows: Probability of the last element is $\frac{1}{2}$ Probability of the next to ...
1answer
1k views

### how to prove optimality of this greedy algo

I need some suggestions on how to prove the below greedy algorithm is optimal. Problem: There are $n$ fires on a road. Each fire $i$ is given as an interval where it starts and ends $[s(i), f(i)]$. ...
1answer
91 views

### Does a Minimum Spanning Tree entail minimum cost between 2 vertices?

In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks
1answer
141 views

### how to prove this scheduling problem

I need some hints for proving the correctness/optimality of the below homework problem. It is a task-schedulding problem with deadlines and penalties. There are n tasks, each of which has a deadline ...
1answer
413 views

### Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
2answers
1k views

### How do I write this proof more formally?

So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree. My Proof: If the graph has unique edge weights, we can ...