One-line summary

In this exercise you determine the time complexity of five functions which calculate a checksum over a given string, which is of length N.

Exercise description

Each of the functions, which are all named checksum_x() (x being a number), gets as parameter a string sentence. It calculates a checksum over the string as the sum of the ordinal value of each character of the string multiplied by its index in the string.

For each of the functions, write as a comment in the file what the time complexity is (immediately below the function), and give a brief explanation on how you determined this. If you do not add an explanation, the answer is automatically considered to be wrong. In your big-O notation of the time complexity, you may use N to refer to the length of the string.

Background information

You may assume the following:

The iterator `range()` is `O(1)`
The function `ord()` is `O(1)`
The function `len()` is `O(1)`
The function `list()` applied to a string of length N is `O(N)`
The function `sum()` applied to a list of length N is `O(N)`
Making a copy of a string of length N is `O(N)`
The method `index()` for a string of length N is `O(N)`
The method `join()` applied to a list of length N is `O(N)`

A brief description of the functions is found in the template file.

# Go over the string by index, and calculate the checksum.
def checksum_1( sentence ):
    checksum = 0
    for i in range( len( sentence ) ):
        checksum += ord( sentence[i] ) * i 
    return checksum

# Go over the string by character, and keep track of the index separately. Calculate the checksum.
def checksum_2( sentence ):
    checksum = 0
    count = 0
    for letter in sentence:
        checksum += ord( letter ) * count
        count += 1
    return checksum
    
# Turn the string into a list of characters, and go over the list by index. Replace each item in
# the list by the ordinal value of the character multiplied by index. Then sum the list.
def checksum_3( sentence ):
    slist = list( sentence )
    for i in range( len( slist ) ):
        slist[i] = ord( slist[i] ) * i
    return sum( slist )
    
# While the sentence still has characters, multiply the ordinal value of the first character by
# a count which is increased by 1 every time. Then make a new string which is a copy of all
# characters minus the first one.
def checksum_4( sentence ):
    checksum = 0
    count = 0
    while len( sentence ) > 0:
        checksum += ord( sentence[0] ) * count
        count += 1
        sentence = sentence[1:]
    return checksum
    
# Go over the string by letter. Determine the index of the first occurrence of the letter. 
# Multiply the ordinal value of the letter by the index. Then turn the sentence into a list
# of letters, and replace the character at the given index by a character which can never 
# occur in a sentence, and finally join the letters of the list again to make a new string.
def checksum_5( sentence ):
    checksum = 0
    for letter in sentence:
        i = sentence.index( letter )
        checksum += ord( sentence[i] ) * i
        slist = list( sentence )
        slist[i] = '\x01'
        sentence = "".join( slist )
    return checksum
    
def main():
    print( checksum_1( "The quick brown fox jumps over the lazy dog." ) ) # 7435
    print( checksum_2( "The quick brown fox jumps over the lazy dog." ) ) # 7435
    print( checksum_3( "The quick brown fox jumps over the lazy dog." ) ) # 7435
    print( checksum_4( "The quick brown fox jumps over the lazy dog." ) ) # 7435
    print( checksum_5( "The quick brown fox jumps over the lazy dog." ) ) # 7435
    
if __name__ == "__main__":
    main()

Note: The submission of this exercise is in markdown and therefore won’t be tested.