what would be the time complexity of this algorithm?-CodePudding

i was wondering what would be the time complexity of this piece of code?

last = 0
ans = 0
array = [1,2,3,3,3,4,5,6]

for number in array:
    if number != last then: ans  ;
    last = number
return ans

im thinking O(n^2) as we look at all the array elements twice, once in executing the for loop and then another time when comparing the two subsequent values, but I am not sure if my guess is correct.

CodePudding user response：

While processing each array element, you just make one comparison, based on which you update ans and last. The complexity of the algorithm stands at O(n), and not O(n^2).

CodePudding user response：

The answer is actually O(1) for this case, and I will explain why after explaining why a similar algorithm would be O(n) and not O(n^2).

Take a look at the following example:

def do_something(array):
    for number in array:
        if number != last then: ans  ;
        last = number
    return ans

We go through each item in the array once, and do two operations with it.

The rule for time complexity is you take the largest component and remove a factor.

if we actually wanted to calculate the exact number of operaitons, you might try something like:

for number in array:
    if number != last then: ans  ; # n times
    last = number # n times
return ans # 1 time

# total number of instructions = 2 * n   1

Now, Python is a high level language so some of these operations are actually multiple operations put together, so that instruction count is not accurate. Instead, when discussing complexity we just take the largest contributing term (2 * n) and remove the coefficient to get (n). big-O is used when discussing worst case, so we call this O(n).

I think your confused because the algorithm you provided looks at two numbers at a time. the distinction you need to understand is that your code only "looks at 2 numbers at a time, once for each item in the array". It does not look at every possible pair of numbers in the array. Even if your code looked at half of the number of possible pairs, this would still be O(n^2) because the 1/2 term would be excluded.

Consider this code that does, here is an example of an O(n^2) algorithm.

for n1 in array:
    for n2 in array:
        print(n1   n2)

In this example, we are looking at each pair of numbers. How many pairs are there? There are n^2 pairs of numbers. Contrast this with your question, we look at each number individually, and compare with last. How many pairs of number and last are there? At worst, 2 * n, which we call O(n).

I hope this clears up why this would be O(n) and not O(n^2). However, as I said at the beginning of my answer this is actually O(1). This is because the length of the array is specifically 8, and not some arbitrary length n. Every time you execute this code it will take the same amount of time, it doesn't vary with anything and so there is no n. n in my example was the length of the array, but there is no such length term provided in your example.