I've been asked to calculate the big theta for a homework assignment, but the lecture material has been a little sparse on this area.
Given the loops
for (x = 1; x <= n; x *= 2){
for(y = 1; y <= n; y += 2)
t++;
I've worked out an execution chart as
x y
1 1, 3, 5, 7 ... n-2, n
2 1, 3, 5, 7 ... n-2, n
4 1, 3, 5, 7 ... n-2, n
8 1, 3, 5, 7 ... n-2, n
log n (n+1)/2
Its the inner loop incrementor that's throwing me off. It executes (n+1)/2 times, so the big theta must be (n log n + log n)/2.
Am I correct?
Your calculations appear correct, but you need to continue a few more steps.
Big theta ignores everything smaller than the biggest term and all constant factors (the equation might help with understanding this).
Theta((n log n + log n)/2)
= Theta(1/2 n log n + 1/2 log n)
= Theta(1/2 n log n)
= Theta(n log n)
Why it ignores constant factors is obvious from looking at the equation (you can just manipulate k appropriately).
Why it ignores everything smaller than the biggest term:
Assume g(x) <= f(x) (from any x onward, since the Theta equation only needs to hold from any n onward)
f(x) <= f(x) + g(x) <= 2.f(x)
Thus Theta(f(x) + g(x)) = Theta(2.f(x)) = Theta(f(x))