Recent content by ATroelstein

Lets say I have M cups and K marbles. All these marbles are blue, except for N of them that are green. At random, I will select a marble and drop it in a cup. The marble will not be returned to the original set of marbles before the next marble is selected. I would like to know the...

I am trying to use Euler's theorem for calculating the following: $$ 8^{7} mod 187 $$ I have determined that: $$ \phi(187) = \phi(11*17) = 160 $$ and $$ 8^{7} = 8^{4} * 8^{2} * 8^{1} $$ but am unfortunately confused about how to now proceed beyond this point. Thank you.

I have generated the graph shown below and now would like to describe it at a high-level according to the curved nature of the plotted line. Besides simply stating observations such as the exponential growth at approximately x = 0.19, is there a classification or term for the shape of the curve...

I have the following equation that I'm trying to simplify: $$\frac{5 + \sqrt{5}}{2\sqrt{5}}*(\frac{1 + \sqrt{5}}{2})^{x} $$ From looking at it, it seems like it could be simplified so that the right-hand side of the multiplication would be: $$(\frac{1 + \sqrt{5}}{2})^{x+1} $$ I started to...

This question is related to the question that I have asked here, although the equation is ever so slightly different: http://www.mathhelpboards.com/f15/solving-specific-variable-when-solving-recurrence-equation-3804/ I have a recurrence equation of the form $$ T(n) = 0, n = 0, n = 1\\ T(n) =...

I have the following recurrence equation, where C is just some constant: $$ T(n) = 0, n = 1\\ T(n) = T(\frac{n-1}{2}) + 2C, n > 1 $$ Using a top-down approach to unrolling the equation to find the pattern, I get: $$ T(n) = T(\frac{n-k}{2^{k}}) + 2kC $$ Now I want to solve for k and associate...

I have the following summation where a is a positive constant and can be > 1 $$ \sum_{k=2}^{n}a^{n-k} $$ I am trying to find a general formula for this summation, which turns out to be a geometric series with a as the common ratio. I have worked out the following: $$ \sum_{k=2}^{n}a^{n-k} =...

The claim I am trying to prove is that if: $$ \lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0 $$ Then f(x) = O(g(x)) using the definition of a limit and then using the definition of Big Oh where the definition of Big Oh is: f(x) = O(g(x)) if and only if there is a constant, c > 0, and an N...

Hello, I am working through some proofs from the following document: Function Definitions Under Calculation of Big - Oh, some theorems are provided that classify the growth rates of functions in relation to one depending on what the limit is as the input approaches infinity. One proof is...

I am trying to solve the following inequality: x3 <= 7x3 - 24x2 + 6x - 10 I have worked it out as follows: 0 <= 6x3 - 24x2 + 6x - 10 10 <= 6x3 - 24x2 + 6x 10 <= 6x(x2 - 4x + 1) At this point, I'm not sure how to proceed and I'm not sure if the factoring on the last step was helpful. Any...

Since i is an integer constant, its asymptotic behavior won't depend on n. The asymptotic behavior of j however will be increasing as n increases, since n = ij. To make my scenario a little more clear, we could look at the case where i = 1. This falls into my scenario and is just one step...

Thank you for your reply CaptainBlack. I am factorizing n because the specific problem I am working on is trying to show that while the case you described is the absolute worst-case scenario, where you have a sub-arrays of size 0 and n-1, that the scenario I gave also has a running time of...

[FONT=Arial]I am trying to prove the following scenario of Quicksort has a running time of Theta(n^2). Initially, we only have arrays of size n, where n = ij. The idea is that at every partition step of Quicksort, you end up with two sub-arrays where one is of size i and the other is of size...

Thanks for the explanation. I have a much better understanding of how to conduct the proof now. I have an additional question now though. In order to turn the summation into the sum, what technique should I be using?

Hello, I have the following recurrence equation $$T(n)=aT(n-1)+bn$$ Using substitution, I have solved it to the following form $$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$ Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this...