On a foggy summer day, Nick took his 3 years old son to the beach. After playing in the sand, the father lost focus for a second, and then realized that his son is gone. Nick didn't know which way his son went, and whether he should first go to the north or to the south. He stayed cool and thought of the following algorithm to search for his son: 1 2 3 i = 1 while the son is not found walk i steps to the north walk back to the starting point walk i steps to the south walk back to the starting point i =i+1 5 6 7 Assumptions: 1. The kid went either to the north or to the south, and he stayed at the same spot till his father found him. 2. Let n be the number of steps Nick has to walk from the staring point to the place his child is. 3. Nick finds his son if he walks at least n steps from the staring point to the direction his son is. a) Find the asymptotic order of the number of steps it took Nick to find his son, as a function of n. Give your answer using the o-notation in the simplest form. b) After he found his son, on their way home, he thought that actually he could have done it faster. He came up with the following variation of the algorithm: 1 2 3 4 5 i = 1 while the son is not found walk i2 steps to the north walk back to the starting point walk iz steps to the south walk back to the starting point i =i+1 7 Find the asymptotic order of the number of steps it took Nick to find his son, as a function of n, if he used this method. Give your answer using the O- notation in the simplest form. c) When he got home, his wife told him that he could have found their son by walking only (n) steps. Describe a variation of this algorithm in which it would take him only (n) steps. (Hint: 1+2+4+8+...+k=2k-1)