Analysis of Computer AlgorithmsTo get into your local grocery store you must wait in line. Outside the front door there are n spaces in a single long row. Each space is either empty or has a single person. Due to social distancing guidelines, people cannot stand in adjacent spaces (i. e. there must be at least one empty space between them). Let S(n) denote the total number of states this line could be in (based on which spaces are occupied or not). For example, S(3) = 5 since the possibilities are {eee, pee, epe, eep, pep}, where 'e' denotes that the space is empty and 'p' denotes that it has a person. Write a recurrence for S(n). Explain why this recurrence is correct. You do not need to solve your recurrence. You should assume S(0) = 1.