I have been given the example:
ALGORITHM 1:
Require: $n \ge 0 $
$x \leftarrow 1$
$\;\;\;\;\;\;$for $i = 1$ to $n$ do:
$\;\;\;\;\;\;\;\;$$x \leftarrow x \cdot i$
$\;\;\;\;\;\;\;\;$ $i \leftarrow i + 1$
$\;\;\;\;\;\;\;$end for
And the time complexity is given by $T(n) = 4n+2$. I understand this to mean that there are 2 assignment statements (hence $+ 2$), and the loop is executed n times, which consists of two assignment statements, as well as two arithmetic operations, giving 4 total operations for each loop (hence $4n$). How do I then go on to find the best and worst case complexity of such an algorithm?
I am now looking at a more complicated algorithm
ALGORITHM 2:
Require: $i \leftarrow 2$
while $i \le \;$ length$(A)$ do
$\;\;\;\;\; j \leftarrow i$
$\;\;\;\;$ while $j >0$ and $A[j-1] > A[j]$ do
$\;\;\;\;\;\;\;\;\;$swap$(A[j], A[j-1])$
$\;\;\;\;\;\;\;\;\;j \leftarrow j-1$
$\;\;\;\;$end while
$\;\;\;\;i \leftarrow i + 1$
end while
In this case, I'm really not sure how to calculate $T(n)$, nor the best/worst case complexity. As far as I can go is to identify that there is 1 initial assignment statement. After that, I get lost looking at all the while loops. Could someone help me understand how to calculate $T(n)$, and the best/worst case complexities? All advice appreciated!