Stack growth and multi-source BFS

Questions 1 to 5 of 8

1. 1. What is the amortised cost of one push on a stack that doubles its array when the array is full?

   O(n), because each push may copy every itemO(1), because the copies average out to a small constant per pushO(log n), because the array halves its size when it fillsO(n squared), because each growth copies the whole stack
2. 2. What is the cost of one push on the linked stack from the first part of the lesson?

   O(n), because the new node must be added at the end of the chainO(log n), because the nodes are kept in sorted orderO(1), because it creates one node and moves the head to itO(n), because the stack copies all its nodes on each push
3. 3. What is the time complexity of multi-source BFS on an R by C grid?

   O(R * C), because each cell joins the queue onceO(R * C * (R + C)), because each cell is searched again from every neighbourO(R + C), because only the edges of the grid are visitedO(sources * R * C), because one search runs from each source
4. 4. Why does the rotting oranges code set a cell to ROTTEN as soon as it is added to the queue?

   So the output prints each minuteSo the empty cells are skipped in the searchSo the minutes counter starts at 1So the same fresh orange is not added to the queue twice
5. 5. What does stack.pop() do when stack is an empty Python list?

   It returns None and the list stays emptyIt raises IndexError: pop from empty listIt returns 0 and the list stays emptyIt removes nothing and returns the last index