Tiberius

I don't think this is a fair way to test the complexity of an algorithm. O(n2) is an upper bound to the running time. In general, the actual T(n) terms could have fractional constants, or could be a very complex polynomial in the number of digits as well. Even in this case, The N2log210 is rounding up a lot of things [for example, as you move down the table, the complexity of addition keeps reducing by a fraction, but it is still O(n)]. I don't think doubling the input length is sufficient to draw conclusions. Look at the graphs of 0.1N2 and NlogN: Clearly, the hidden constants in the big O notation are relevant when you have small input sizes of 14 and 12, and you are simply doubling them. I guess if you raise the input size to a sufficiently large power, then it might be a good indication of the complexity. (say N^5 ?) I'm just learning this stuff, so I could be wrong.

Ah, yes, that would make sense. For some reason I believed that addition was a constant time operation. How silly of me. So K=Nlog210, and a bunch of O(N) additions for each pass in the worst case--- O(N2) Got it, thanks.

I was looking up the fastest multiplication algorithms on Wikipedia. Karatsuba showed up [O(N1.585)], Strassen showed up[O(N log N log log N)], all with respectable big O scores, but a friend recently told me of an algorithm that seems to work in linear time (wrt to the number of digits in the numbers). I can't seem to find it on Google, so I'll just describe it here with an example: Suppose you have two numbers 141 and 45 and we want to multiply them. We keep dividing the first number by 2 until it becomes 1 (integer division), and keep multiplying the 2nd number the same number of times. 141 45 70 90 35 180 17 360 8 720 4 1440 2 2880 1 5760 Now, we look at the LHS and add up all the terms that correspond to ODD terms on the left: 45+180+360+5760=6345 which is 141*45 Now as far as I could tell, there is a linear relationship between the number of iterations of division before you get down to 1 and the number of digits. (You end up adding 3 or 4 iterations per digit increase because multiplying by 10 is multiplying by 1010 in binary). The relationship is something like K=3.322N +0.5, where N is the number of digits and K is the number of iterations. ( I wasn't too sure of a mathematical approach to the relation between K and N, so I plotted K vs N for N=1 to 600 and found that a linear relationship existed) So in the worst case, for an N digit number, one has to do K multiplications by 2 and K divisions by 2. During the process, one has to do at max (if all LHS terms are odd) K additions as well. [Multiplying/Dividing a number by two is a constant time operation right ? Just a simple bit-shift ?] So shouldn't the overall run-time be O(2K+K) =O(9.966N+1.5) = O(N) ? Am I missing something here ? Can I consider division by 2 as a constant time operation as well ? I assumed it was because bit-shifting seems like something that would be classified as constant time, just as adding zero's in Karatsuba's algorithm was considered a constant time operation. Is there something wrong with the relationship between K and N ? Will it deviate for higher values on N ? (I couldn't really go beyond 600, nor could I derive a formal mathematical relationship).

I forgot I put this up... Thanks mathematic !

Hi, I am trying to prove that a limit exists at a point using the epsilon delta definition in the complex plane, but I can't seem to reach a conclusion. Here's what I have been trying to get at: [LATEX]\lim_{z\to z_o} z^2+c = {z_o}^2 +c[/LATEX] [LATEX] |z^2+c-{z_o}^2-c|<\epsilon \ whenever\ 0<|z-z_o|<\delta[/LATEX] [LATEX]LH=|z^2-{z_o}^2|=|z-z_o||z+z_o|[/LATEX] [LATEX]=|z-z_o||\overline{z+z_o}|[/LATEX] [LATEX]=|z-z_o||\bar{z}+\bar{z_o}|[/LATEX] [LATEX]=|z\bar{z} +z\bar{z_o} -{z_o}\bar{z} -z_o\bar{z_o}|[/LATEX] [LATEX]=| |z|^2 -|z_o|^2 +2Im(zz_o) |[/LATEX] [LATEX]\leq||z|^2 -|z_o|^2 +2|z||z_o|| \ (because\ Im(z)\leq|z|)[/LATEX] But I can't get any further. I did this much thinking I could factor it to the square of delta, but that didn't work out because of the positive 2zzo term.If anyone can help me out here, it would be great. Thanks.

Here are the two sets of questions that I had asked earlier: The first set(with hypervalent_iodine's answers in orange): The second set: Thank you.

Sorry, I didn't see your post before, but you answered my question spot-on. Thanks.

Great ! Thanks. From what I understood of what you said, this is what happens: Glu is the rest of the glutamate anion. So there's only one COOH group involved ? I was browsing around trying to find out the mechanism before I saw your reply and I stumbled across this: This mechanism involves both aspartate and glutamate, but the description kind of confuses me.. I'll quote the mechanism from the article. I don't understand where this 'nucleophilic attack' comes in and which molecules are involved... Thank you.

Hello, On the PDB site, it says that "...glutamate 233, aspartate 197, and aspartate 300 work together to cleave the connection..." Is there a generalized mechanism of some sort for this sort of cleavage ? Because I can't figure out how these groups are capable of breaking bonds... The wikipedia article on enzyme catalysis has a section on electrostatic catalysis which seems to be relevant to amylase, but I can't figure out how it applies in this case. From the example that is there in the wikipedia artice, The metal atom forms co-ordinate bonds with the O of water and another atom of the substrate. This extra bond makes the substrate bond(in amylase's case the glycosidic bond) weak and it breaks off, allowing hydrolysis. I can't see where these glutamate and aspartate groups come into the picture... Thanks.

I was looking over the mechanism of alpha amylase hydrolysis of starch. It seems that a particular pair of glucose monomers are held in place with hydrogen bonds by the amylase enzyme. The molecule bends due to these bonds thus lowering the energy required to cleave the glycosidic bond between them. My question is, what locations on the amylase enzyme and the starch polymer does the hydrogen bonding take place ? I found a representation of what goes on: It shows the starch held in place.... Where are these bonds made to keep the molecule in place ? I know its probably a stupid question because amylase looks like this but it would be interesting to know if the answer is out there.... Thank you.

Thanks for your reply. I may get access to column chromatography facilities in a BSc Chem Lab... Assuming I do, could you point me to a link for the method ? Also, do you have any experience with crystallizing out(and growing) thermally unstable proteins like alpha amylase ? Thank you.

I wanted to perform some experiments on enzyme rates and chose amylase as it is easy to obtain. However, I wanted it in pure form so that I can perform mass/concentration-based calculations as well. Is there any way to extract alpha-amylase from human saliva? Thank you.