DSA 5: Big O - String Select Function

1. \(Time\ complexity\) of select_a function using \(Big\ O\) notation

def select_a(array):
    new_array = []
    for string_str in array:
        if string_str[0] == "a":
            new_array.append(string_str)
    return new_array

input_arr = ["aa","ba","cd","ab","32","a1"]
select_a(input_arr)

['aa', 'ab', 'a1']

2. My Written Solution

2.1 \(Search()\) whole list of arrays \(N\):

• \(Search_{all-cases}\): N steps
• or \(O(N)\)

2.2 \(Compare\_and\_Insert()\): \(test\) string[0] is a, then \(Insert()\) into new_array (if True)

• \(Insert_{best-case}\): 0 steps (e.g. zero insertions)
  
• \(Insert_{worse-case}\): N steps (e.g. insert every string in array)
  • Note: \(Big\ O\) always takes the \(worse-case\)
    
  • Thus, \(O(N)\)

2.3 \(Big\ O\) (Total Steps of Worse-Case)

• \(O(Search) + O(Compare\_and\_Insert)\)
  
• \(O(N) + O(N)\)
  
• \(O(2N)\)
  
• \(O(N)\)