How many steps and big-O complexity

Question

def percentBases(dnaStrand):
    cytosine = dnaStrand.count('C')
    guanine= dnaStrand.count('G')
    adenine= dnaStrand.count('A')
    thymine= dnaStrand.count('T')
    
    percentC = round(cytosine/len(dnaStrand)*100,2)
    percentG =  round(guanine/len(dnaStrand)*100,2)
    percentA = round(adenine/len(dnaStrand)*100,2)
    percentT = round(thymine/len(dnaStrand)*100,2)
    
 
    return(percentC, percentG, percentA, percentT)

I have written this simple code and have been asked to record an approximate time complexity using big-O notation. I don't have a clue about big-O notation but after reading I would have a guess at: T(n) = 8 O(8)

Please correct me if I'm wrong and try to explain to me. Thanks

I'm no expert, but think your guess is correct. – martineau Dec 10 '20 at 17:34 — martineau, Dec 10 '20 at 17:34

score 2 · Answer 1 · answered Dec 10 '20 at 17:47

To understand big-O time complexity of a function, you need to look at what will take more time to compute as the size of the input changes. Your input dnaStrand is a string, and you do two operations count and len that could potentially take more time as the length of the input increases. len for a string is constant (source), but count is linear, since you have to loop over the entire string to count occurrences of different substrings. So, your function is 4*O(n), or just O(n).

score -1 · Answer 2 · answered Dec 10 '20 at 17:47

-1

Your function performs 8 operations and all of them take constant time. So, T(n) = 8

In terms of big-o, you can write it as T(n) = O(1) or O(c)

answered Dec 10 '20 at 17:47

umar

389
3
11

`len` is constant, but `count` is linear. – Bill the Lizard Dec 10 '20 at 17:49
Bill the lizard so only the four assignment statements containing the count method are counted? And not the other four assignment statements? And is T(n) = 8 correct for the first function? – Stephen19058 Dec 10 '20 at 18:05

How many steps and big-O complexity

2 Answers2