How to determine the time complexity for the following algorithms?

Question

I have a midterm tomorrow and am having a hard time understanding the following time complexity problems.

1.

Algorithm foo(n)
     i←0
     j←0
     while i<n do {
         if j=i then j←j+1
         else if j=2i then i←n−j
         else {
             i←i+1
             j←j+1
         }
     }

Which is O(1)

2.

Algorithm foo(n)
     i←0
     j←0
     while i<n do {
         if i=k then {
             A[i]←k
             k←k+1
             i←1
         }
     }
     else i←i+1

Which is O(n^2)

So basically, how I've been solving these types of questions is to find the parts of the algorithm that perform a constant number of operations. For algorithm 1, this would be the variables and what's inside the loop:

C1:

i←0
j←0

C2:

if j=i then j←j+1
         else if j=2i then i←n−j
         else {
             i←i+1
             j←j+1

Then, I count the number of iterations of the loop, n, and add it to the formula:

f(n) = C1+nC2 is O(n) (WRONG ANSWER)

I can tell that my issue is that I'm miscounting the number of iterations for both of these loops. If someone could let me know if my thought process here is completely wrong and/or how I should be counting the loop iterations it would be much appreciated.

Answer 1

Did you implement the algorithms and just looked at what happens? You should, if you haven't yet.

Example 1

def bigo_one(n):
    print(f"n == {n}")
    i = 0
    j = 0
    while i<n:
        if j==i:
            j = j + 1
        elif j == 2 * i:
            i = n - j
        else:
            i = i + 1
            j = j + 1
        print(i, j)

bigo_one(10)
bigo_one(100)
bigo_one(1000)

output:

n == 10
0 1
1 2
8 2
9 3
10 4
n == 100
0 1
1 2
98 2
99 3
100 4
n == 1000
0 1
1 2
998 2
999 3
1000 4

From the output it's easy to see what ALWAYS happens, independent of n:

1. j increases to 2
2. i jumps to n-2
3. i increases to n

Which are always 5 steps -> O(1)

Example 2

def bigo_nsquare(n):
    print(f"n == {n}")
    i = 0
    j = 0
    while i<n:
        if j==i:
            j = j + 1
            i = 1
        else:
            i = i + 1
        print(i, j)
        
bigo_nsquare(2)
bigo_nsquare(4)
bigo_nsquare(10)

output:

n == 2
1 1
1 2
2 2
n == 4
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4
n == 10
1 1
1 2
2 2
1 3
2 3
[...]

This loop is stepping through the lower triangle of a square matrix so it's plausible that it has O(n²) complexity.