What is time complexity?

Given an algorithm with some input, we want to know how much time will it take depending on some characteristic of input. Usually we’re interested in the size of input but in artificial examples we often see an explicit input parameter n.

So, how much time will it take for a given n? Impossible to tell. Our algorithm may be running on a faster or slower processor, the code may be compiled with a good or a bad compiler and so on. In order to have some answer, we cheat: we consider that every operation in our algorithm takes one or several “units” / “steps” of time and count those. For example, for some hypothetical algorithm total time may be T(n) = n^3 + 11n^2 - 4.

Furthermore, we need this to describe and compare algorithms, and also for our estimate to not change if we make some “minor” modifications. As it turns out, rounding “exact” functions to their Big-O classes tends to solve both problems (except that in programming we often want to “glue” all O(a^n) classes into one, dubbed “grows too fast to be practical”).

How do we compute time complexity?

We start with “prices” for some basic actions our algorithm consists of and then we add them together. Most of the time, we consider the cost of any operation written with a single operator sign to be 1 unit. In fact, the very important feature of the “array” data structure is that element access has a constant cost: T("x[n]") = const. However, in your case your teacher seems to imply that the cost of a^n is in O(n). I’ll assume it’s n-1.

Every function, too, has a price. Thus, we usually can read the function and write the equation:

function compute_polynomial_recursive(x, n):
    if n == 1:
        return x 
    else:
        return (x[n]^3) + compute_polynomial_recursive(x, n - 1)

T(1) = 2; T(n) = 1 + 1 + (3-1) + 1 + T(n-1) + 1 + 1 | n>1. (I’m counting return as a time loss but function call as “free”.) Given these equations, it’s easy to obtain the “closed-form” expression for T(n):

T(n) = 7 + T(n-1) = 7 + 7 + T(n-2) = ... = 7*(n-1) + T(1) = 7n-5. Once you’ve obtained that, you can also write the O-class: T(n) = O(n).

In the second example, we have a bit more tricky expression.

function compute_polynomial_recursive(a, n):
    if n == 1:
        return a^1 
    else
        return (a^n) + compute_polynomial_recursive(a, n - 1) 

T(1) = 2; T(n) = 1 + (n-1) + 1 + T(n-1) + 1 + 1 = (n+3) + T(n-1). Once again, we can simply collapse the expression: T(n) = (n+3) + ((n-1)+3) + ... + (2+3) + 2 = n^2/2 + 7n/2 - 2 (self-check: T(1) is still 2). In Big-O notation, T(n) = O(n^2). Intuitively, this time around the amount of work in the first calls grows with n so the whole computation is slower.

(In both cases, these are bad recursions: you generally want the function call to be your last instruction before the return, but that has to do with memory complexity: these function as written can easily run out of stack space.)

Can we skip this “count every single operation” mess?

Kinda. You can keep track of only O-classes – in which case for every string of consecutive operations you need to take into account only the asymptotically slowest of them. But you need to be careful that the omitted multipliers in different summands are the same (or, at least, can’t grow arbitrarily large):
n + 2*(n-1) + 3*(n-2) + 4*(n-3) + ... = O(n) + O(n-1) + O(n-2) + ... = O(n^2) but if you explicitly write the sum as a function of n it turns out to be O(n^3). Oops?

Until you feel confident that you can eyeball these expressions, I would recommend to at least try and write the “exact” times. It is also practical in a sense that you need to pay some attention to those “constant” factors in real optimization anyway.

Can we use induction?

Yes, but definitely not as shown in the example.

function F(n):
    if n == 1:
        return 1;
    else
        return 1 + F(n);

“Reasoning”: suppose T(n) = O(n^3). Then T(n+1) = 2 + T(n) + 1 = O(n^3) + 3 = O((n+1)^3) (since O(n^3) and O((n+1)^3) is the same class). Thus, T(n) = O(n^3).

Real reasoning: suppose T(n) = O(n^3) = k*n^3 + o(n^3) (notice the small o!). Then we need to prove that T(n+1) = k'*(n+1)^3 + o((n+1)^3. We try – T(n+1) = 2 + T(n) + 1 = k*n^3 + 3 + o(n^3) ≠ k'*(n+1)^3 + o((n+1)^3) – and we fail. On the other hand, assumption T(n) = O(n) succeeds: T(n+1) = k*n + 3 + o(n) = k*(n+1) + (3-k) + o(n) = k*(n+1) + o(n+1).