There are several groups of test cases. One group is for low positive numbers. These are largely fixed (i.e. fib(0), fib(1), fib(10), etc) but some are random. Another group is for low negative integers, again, some fixed and some random. The last group is for higher n, generally n > 1000, with the last two tests for n > 1,000,000. Like the other groups, some inputs are fixed and some are random. This last group has the tests that tend to timeout. Note that failing anything within a group stops the testing at the end of the group. In other words if you fail something in the low positive numbers group, you don't ever see any tests from the negative or high positive numbers groups.

While your algorithm may be correct, if you are getting timeouts you may want to try some testing on you local machine. If fib(1000000) takes more than a few seconds, your algorithm is probably too slow and you need to rethink it.