Análise de Loops em Complexidade de Algoritmos

NOTE:
Eu sei que existe muito material sobre algoritmos na internet, mas eu acredito que essas minhas questões são cruciais para os iniciantes.

Para começar, imagine que nós temos os seguintes loops for() e while()

Linearsearch(arr, n, key)                                 
{                                                       
    i = 0;
    for(i = 0; i < n; i++)    // n + 1? or n?
    { 
        if(arr[i] == key)
        {
            printf(“Found”);
        }
}

i = 1;
sum = 0;        // Cost  Times
while (i <= n)  // c3    n + 1? or n?
{
    i += 1;
    sum += i;
}

• Por que os loops for() e while() tem o tempo "n + 1" e não apenas "n"?
• Em Python os loops for() e while() também são "n + 1"? Ou apenas "n"?

def linear_search(arr, n, key):  # (n + 1)? or (n)?
    for i in range(n):
        if arr[i] == key:
            print("Found")

i = 1
sum = 0
while i <= n:
    sum += i
    i += 1

---

O custo das instruções dentro dos loops for() e while() é "n" vezes ou seu custo específico?

Por exemplo, vamos considerar os seguintes loops for() e while():

def linear_search(data, value):
    for index in range(len(data)):
        if value == data[index]:
            return index
    raise ValueError('Value not found in the list')

i = 1;
sum = 0;
while (i <= n)
{
    i += 1;
    sum += i;
}

As instruções dentro dos loops tem sempre "n" custo ou depende? Isso porque eu vi em um tutorial na internet um caso em que as instruções dentro de um loop while tem tempo "n":

                // Cost  Times
i = 1;          // c1    1
sum = 0;        // c2    1
while (i <= n)  // c3    n + 1
{               //
    i += 1;     // c4    n
    sum += i;   // c5    n
}               //

def linear_search(data, value):     # Cost  Times
    for index in range(len(data)):  # c1    n
        if value == data[index]:    # c2    n
            return index            # c3    1 (or n?)
    raise ValueError('Value not found in the list')

• Veja que as instruções c4 e c5 do loop while() são "n" e não constantes(1). Por que?
• E a instrução c3 no loop for() é constante(1) e não "n"?

---

As instruções dentro dos loops são multiplicadas pelo número de iterações?

Para entender esta questão, vamos considerar o seguinte loop for():

def traverse(self):
    for index, _ in enumerate(self.arr):
        print(f"Index: {index}, Item: {self.arr[index]}")

• O loop "for" itera "n" vezes, então sua complexidade é O(n).
• Dentro do loop, a operação de impressão tem complexidade constante O(1).
• Como o loop se repete "n" vezes, o custo total se torna: n x O(1) = O(n).

A afirmação acima está correta?

Se a afirmação acima estiver correta, o loop aninhado abaixo será:

                        # Cost  Times
for row in matrix:      # c1    n
    for column in row:  # c2    n * n
        print(column)   # c3    1? or n?

So:

Total Cost = n + (n x n) + 1
           = n + n^2 + 1
           = O(n^2)