Time Complexity

[The Hobo]

How do I find out the time complexity for:

T(n) = 1 if n <= 4
1 + T(n-4) for n > 4

n is even

Any help is appreciated.

[krtxmrtz]

How do I find out the time complexity for:

T(n) = 1 if n <= 4
1 + T(n-4) for n > 4

n is even

Any help is appreciated.

Though I've studied math I'm not familiar with the term "time complexity", maybe I know the Spanish version under quite different words, but I'm interested...

[Phenix]

I suppose he means this http://www.csc.liv.ac.uk/~ped/teacha...r/complex.html for optimizing his coding.

[twanvl]

You reduce n by a fixed amount until you reach a value <4, so that is O(n) steps. Or do you mean that T(n) is the complexity and you want to reduce it to a big oh notation?

[The Hobo]

I know it goes something like:

T(N) = 1 + T(N - 4)
T(N - 4) = 1 + T(N - 8)    T(N) = 1 + (1 + T(N - 8))
T(N - 8) = 1 + T(N - 12)   T(N) = 1 + (1 + (1 + T(N - 12)))

But I don't know why, or what my result is supposed to look like...and I can't find anything on the web to help. Any have any ideas?

[twanvl]

You should look at it the other way around:
T(n) = 1 for 0<n<=4
T(n) = 2 for 4<n<=8
T(n) = 3 for 8<n<=12
You can now substitute T(i):
a = T(n) = 1 for 4*a-4<n<=4*a
b = T(n) = 2 for 4*b-4<n<=4*b
c = T(n) = 3 for 4*c-4<n<=4*c
So, given T(n) you can caluculate the range of minn<n<=maxn:
minn(T(n)) = 4*T(n)-4
maxn(T(n)) = 4*T(n)
Now to reverse this function you need to map a range to a single number, this can be done with the ceil function (roundig up) and a division:
T(n) = ceil(n/4)