Please answer the following questions using the images provided:

1: what would be a worst-case string and substring example for the brute force string search and what would be the Big O time complexity for the worst case?

2: what would be the best-case string and substring example for the optimized string search and what would be the Big O time complexity for the best case?

the programming language is C

a. A brute force way to find a substring within another is to search a string one character at a time until a character matches the first character of the substring as in the example shown below. i. Find sub = "carrot" in s = "Bob likes cars and carrots" 1. Compare B to c-mismatch 2. Compare o to c-mismatch 3. Compare b to c-mismatch 4. Compare space to c-mismatch 5. 6. Compare space to c-mismatch 7. Compare c to c-match (at "cars" in s) 8. Compare a to a-match 9. Comparer tor-match 10. Compare stor-mismatch, start back at the "a" in "cars" 11. Compare a to c-mismatch 12. Comparer to c-mismatch 13. Compare s to c-mismatch 14. Compare space to c-mismatch 15... 16. Compare c to c-match 17. Compare a to a-match 18. Comparer tor-match 19. Comparer tor-match 20. Compare o to o-match 21. Compare t tot-match 22. Return location 19 in s . ii. Think about how to optimize the search so the search algorithm does not have to go back to the "a" in "cars" on a mismatch, such as 1. Compare B to c-mismatch 2. 3. Compare c to c-match 4. Compare a to a-match 5. Comparer tor-match 6. Compare stor-mismatch (since "c" was not encountered again, start at the space after "cars") 7. Compare space to c-mismatch 8. b. Example output for the brute force search function: i. Search for 'carrot' in 'carro carro carro carro' - location-1 ii. Search for 'carrot' in 'carrot carro carro carro' - location o iii. Search for 'caccoc' in 'cacco cacco caccoc cacco' - location 12 C. Example output for the optimized search function with a trace of the i index variable that traverses strings: i. substring - i = 0 ii. substring - 1 = 6 iii. substring - i = 12 iv. substring - i = 18 V. Search for 'carrot' in 'carro carro carro carro'-location-1 vi. Substring -i = 0 vii. Search for 'carrot' in 'carrot carro carro carro'-location O viii. substring - i = 0 ix. substring - 1 = 2 X. substring - i - 3 xi. substring - 1 = 4 xii. substring - i = 5 xiii. substring - i - 6 xiv. substring - i = 8 xv. substring - i = 9 xvi. substring - i = 10 xvii. substring - i = 11 xviii. substring - i = 12 xix. Search for 'caccoc' in 'cacco cacco caccoc cacco' - location 12