Question

Big O run time of algorithm

2 Super Mario Run A Mario world M consists of a k × k grid. Each field in the grid is either empty or brick. Two empty fields are marked as start and goal (see Fig. 2(a)). The goal of the game is to move the player, called Mario, from the start field to the goal field. When Mario is in field (x, y) he has the following options Forward Mario moves to the field (x + 1,y). This move is possible if (x + 1, y) is empty and (x+1,y-1) is brick. Jump Mario moves to the field (x +1,y +2). This move is possible if the fields (x, y +2), (x,y +1), and (x +1,y +2) are empty, and (x + 1, y +1) is brick. Fall Mario moves to the field (x 1,y') where y < y is the maximal value y' such that (x +1,y' 1) is brick and (x +1,y), (x +1,y -1),..., (x +1,y) are empty. For instance, Mario in field (4,4) can move forward to (5,4) or jump to field (5,6). A move is valid if the move can be done according to the above rules. All fields that can be reached via valid moves from the start field are the valid fields. For example, (4,4) is a valid field, since it can be reached from the start field in (1,2) doing the sequence of valid moves forward, forward, jump A Mario world M defines a directed graph G with n vertices and m edges (see Fig. 2(b)). All valid fields correspond to a vertex and the valid moves define the edges (there is an edge from field (x,y) to field (x',y') if Mario can move from (x,y) to (x',y') with a valid move). The edges corresponding to forward, jump and fall are denoted by forward edges, jump edges and fall edges. 2.1 Let M be a Mario world defined on a k × k grid and let G be the corresponding Mario graph. Indicate the maximum number of nodes n that can appear in G as a function of k Solution: 2.2 let M be a Mario world defined on a k × k grid and let G be the corresponding Mario graph. Indicate the maximum number of edges m that can appear in G as a function of k Solution:

Answer 1

2.1- the answer is 6. i.e. o(2^k)

2.2- the answer is the first option i.e. o(log k)