Recent content by kasper_2211

Here is a, maybe, better attempt at a solution. 1. Homework Statement I am trying to solve this here recurrence : T(n)=T(n-1)+O(n lg n). I am trying to do it by guessing the solution, and then use substitution to prove it right. I think that I am way off though...2. Homework Equations...

Homework Statement I am trying to solve this here recurrence : T(n)=T(n-1)+O(n lg n). I am trying to do it by guessing the solution, and then use substitution to prove it right. I think that I am way off though...Homework Equations T(n)=T(n-1)+O(n lg n). lg n = log_2 nThe Attempt at a Solution...

Oh, thanks a lot for the reply. I've never heard of similar matrices before (this is my first week of linear algebra), but i looked it up and it got me going. So yeah, thanks.

Homework Statement Given 3 matrices C, D, F and another matrix A, can i say anything in general about the relationship between C.D^n.F and A^n if i know that F = C^-1 and that C.D.F = A. Homework Equations The Attempt at a Solution For example, If C.D.F = A then (C.D.F)^2 = A^2...

Obviously my "proof" is not correct. Just forget it.

Homework Statement Given an algorithm A i need to figure out a formula that can be used to prove that the algorithm is O(logN). I will try to avoid the details of the algorithm, since i need help with the math only. I think all you need to know is that A takes two arguments i and j. So you...

Thanks alot! I think i got it now. I will post the final proof here when the homework is turned in (don't want to get in trouble for posting the final solution before that). But thanks a lot for the help.

Or maybe i need to show that if I call A with j - i < 2^(n+1), then for the first recursive call j - i will be less than 2^n, and then by the induction hypothesis that will imply A(i, j) <= n which is less than n + 1?? The first step in the algorithm is to cut the list in half...so when i call A...

Ok, so now i "completely" understand the logic behind the proof. Show basecase, j - i < 1 => A(i,j) <= 0 Now assume that, j - i < 2^n => A(i, j) <= n for some arbitrary n. This is the induction hypothesis. Now assume that, j - i < 2^(n+1) and show that this implies A(i, j) <= n +1 BUT, i...

Thanks! That got me started! I can find and prove the base case. I did not write it in the problem statement, but by definition a call A(i, i) = 0. So if j - i < 1, then j = i and then A(i, i) = 0. So the base case is ok. So, i guess for the next part i need something similar. I am still...

Yeah, i wish i could explain things better. The way the algorithm is called is by A(1, N), where N is the length of the sequence T (the algorithm is not actually given a list T as input, since it's not "a real algorithm"). So N = 12 in the example A(1, 12). The algorithm is given parameters 1...

I pushed the wrong button and published some gibberish before i was finished writing. Sorry about that.

Homework Statement The problem statement is as follows: Let T be a ordered list(sequence) with N entrys. Prove by induction that, j-i< 2^{n} \Rightarrow A(i,j) \leq n for all integers i, j, n where 1 \leq i \leq j \leq N and n \geq 0 A(i, j) is the number of steps taken by a certain...