O(n) - Space and Time - Complexity of Algorithm

talking about books on the topic, I'd recommend :

Introduction To The Theory of Computation 2nd edition (Sipser)
and Computational Complexity (Papadimitriou)

both can be found on amazon. You can't really use them as first look into complexity, because they are too... complex, but they are really good references. You should also have a look on The Art Of Computer Programming from mighty Donald Knuth, who references many algorithms that are the most efficient given your needs.

Otherwise, sunnycoder and nag9s2007 told it right, all that can be added is a little example of what that actually means.

take this algorithm :

z := 1
for i =1, i <= n, i := i+1 do
    z := z + z
done

to calculate z, you need to execute n times the loop, therefore, it is a linear complexity, so O(n).

now, take this one :

z := get_user_input()
i := 1
while i <= n do
    i := i +1
    z := z + z
    if z > arbitrary_maximum_limit then
        break
    endif
done

you'll iterate n times over the while loop, except if z is bigger than arbitrary_maximum_limit. But it is still an O(n) algorithm. Because O(n) can be considered as the 'worst case scenario' in term of time (or memory when talking about space complexity).

About space complexity, the example is quite the same :

function foobar(n):
z := array
for i =1, i <= n, i := i+1 do
    z.append('foo')
done

now, z contains n times the string 'foo'. So the algorithm needs as much memory cells as given by the value of n. The algorithm is O(n) in space. You can notice that 'foo' (if it were a C string) takes 4 memory cells (foo + \0), so it actually takes 4*n memory cells, so why don't we say O(n*4) ? because we just don't care about constants, what we care about is how the algorithm grows.

finally, to illustrate the time/space tradeoff both sunnycoder and nag9s2007 talked about, you could rewrite the first algorithm that way :

z = 1
y = z
for i=1, i <= n/2, i := i + 1 do
    z := z + z
    if z != n/2 then
        z := z + z
    end
done

now we increased the algorithm efficiency by a factor 2, so you can say it costs O(n/2), therefore, it is still growing in O(n). To increase the efficiency, we had to take 2 times more memory (ie two variables instead of one).

Of course my example is pretty stupid, but I thought it could be useful to show you one. Also, this is only the surface of a whole theory (described in the books I talked about earlier) about time and space complexity. Have good readings, and see you at your next question, that could be "what is the P vs NP problem ?" :p