Proving a tight bound on the worst case running time of an algorithm?

Question

This exercise

I don't understand what 'give a tight bound' implies here.

The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it is correct?

The definition is the following

There exists a number n that after a Breakpoint B, that for two functions f(n) and g(n), if n is equal or greater than B, then there exist a constant c such that f(n) <= c g(n)

But what is G(n) and what is F(n) here?

Answer 1

A tight bound means that you need to find a function $f$ such that $f$ is both an asymptotically upper and lower bound for the running time of your algorithm. In big O notation this is usually denoted $\Theta$. When considering the asymptotical running time of an algorithm, you usually work in a model that specifies some operations you can use and the cost of these operations(often just 1) then the running time of the algorithm for a given input is the sum of costs of all the operations used when the algorithm is run on the given algorithm. For example look at the following algorithm:

1. $i \leftarrow 0$
2. while $i < n$
3. $\quad i \leftarrow i+2$
4. return $i$

And consider the model where we are interested in the number of additions, so we assign a cost of 1 to the addition operation, and all other operations are free(comparison, assignment, looping constructs). Note that I'm not claiming this is a realistic model of how the running time on a computer behaves. So in our case $f(n)$ is the number of additions performed when the input is $n$. It is not hard to see that $f(n) = \lceil \frac{n}{2} \rceil$. So the asymptotic running time is $\Theta(f) = n$, since $\frac{1}{2}n \leq f(n) \leq n$.

Now there's one big difference between this example and your example, the input to your function is not just a number $n$, but a list $A$ such that $n = \mathrm{len}(A)$. Hence why we consider the worst case running time, that is for a given $n$ we consider the list $A$ such that the running time(i.e. sum of costs like above) is as big as possible. Think of it as maximising the running time by crafting $A$ in a bad way like if you were an opponent trying to stall the computer for as long as possible.

So in you case the described algorithm has basically 2 branches, and one good strategy would be to consider the running time of each of these branches and see which one is worst, then after that consider if you can get into the "bad" branch.

Furthermore note that in an informal setting, often you won't actually try to count something like the additions explicitly but simply the number of lines executed(where you count a line multiple times in the sense that if you pass over line 12 100 times, it counts as 100 lines executed).