DSA 8: Big O - Analysing Algorithms

1. \(4N + 16\) Steps

1.1 Tony’s Solution: \(O(N)\)

\(O(4N+16) \rightarrow O(4N) \rightarrow O(N)\)

2. \(2N^2\) Steps

2.1 Tony’s Solution: \(O(N^2)\)

\(O(2N^2) \rightarrow O(N^2)\)

3. double_then_sum Function

​def​ ​double_then_sum​(array):
    doubled_array = []
    ​for​ number ​in​ array:
        doubled_array.append(number * 2)
    sum = 0
    ​for​ number ​in​ doubled_array:
        sum += number
    ​return​ sum

3.1 Tony’s Solution: \(O(N)\)

• Loop through array: \(N\) steps
  
• Loop through doubled_array: \(N\) steps
  
• Total steps: \(2N\)
  
• Big O: \(O(2N) \rightarrow O(N)\)

4. mutiple_cases Function

​def​ ​multiple_cases​(array):
    ​for​ string ​in​ array:
        ​print​(string.upper())
        ​print​(string.lower())
        ​print​(string.capitalize())

4.1 Tony’s Solution: \(O(N)\)

The function performs multiple operations on each string in the input array:

• \(3\) operations or steps per string or \(N\)
  
• Total Steps: \(3N\) steps
• Big O: \(O(3N) \rightarrow O(N)\)

5. every_other Function

​def​ ​every_other​(array):
        ​for​ index, number ​in​ enumerate(array):
            ​if​ index % 2 == 0:
                ​for​ other_number ​in​ array:
                    ​print​(number + other_number)

5.1 Tony’s Solution: \(O(N)\)

• \(N\) operations to iterate through array
• \(N/2\) operations applies in the if statement
• Total Steps: \(N*N/2=N^2/2\) steps
• Big O: \(O(N^2/2) \rightarrow O(N^2)\)