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...