Can someone explain this to me? Such as this:
Given a function:
for k = 1 to lg(n) for j = 1 to n x=x+1
How would I analyze the tight (Θ) bound?
+2
A:
Your function is Θ(log n · n): The outer loop is repeated log n times and the inner loop n times (for each iteration of the outer for), so x=x+1 is executed log n · n times in total. And since the number of repetitions is fixed, the lower and upper bound is the same.
Gumbo
2010-05-24 22:16:02
I have another question how would I handle a situation if the inner loop is for j = 1 to kˆ2.I know the answer is n^3. but how would I prove something like thishow would I apply it to something like that?
tomwu
2010-05-25 00:26:25
@tomwu: There are two different cost measures: The uniform cost measure, that measures one unit per basic operation; and the logarithmic measure, that measures each instruction based on the actual computational costs. While the latter is more precise, the former is often preferred as it’s obviously simpler to work with. So the first step is to rate each statement with its costs. The rest is math: consecutive operations are added and repeated operations are multiplied. For our example we could say log *n* · (*n* · (3)) while each pair of parentheses represent one `for` body in our algorithm.
Gumbo
2010-05-25 07:05:37
The 3 is derived from the three operations in `x=x+1`: reading *x*, adding 1 to it and writing *x* back. So to be exactly, our function is Θ(log *n* · *n* · 3). But the static 3 can be omitted and the remaining is Θ(log *n* · *n*).
Gumbo
2010-05-25 07:09:09