This discussion is to help you prepare for the final exam, which is worth 30% of your final grade. That's almost as much as all the projects combined, so it is well worth your time to prepare. For this discussion, you will create a potential question for the final exam and answer it. You should then be able to look at the questions others created to help prepare you for the final exam. We will use this discussion as inspiration for creating the final exam, so some of the questions may be quite similar to the questions created by your classmates.
What is the BigO notation for accessing the last element in a linked list of n elements using only a pointer to the first element in the array?
a) O(1)
b) O(n)
c) O(n^2)
d) None of the above
What is the BigO notation for accesing the last element in a linked list of n elements using only a pointer to the last element in the array?
a) O(1)
b) O(n)
c) O(n^2)
d) None of the above
What is the best case scenario for finding an element in a n x n matrix? What is the worst case?
a) O(log(n)) : O(1)
b) O(n^3) : O(n)
c) O(1) : O(n^2)
d) None of the above
What is the worst case scenario for finding one of the nodes of a full binary tree with n elements?
a) O(1/n)
b) O(log(2^n - 1))
c) O(n^2)
d) None of the above
ANSWERS:
1) To find the last node of a linked list one must use the pointer at the beginning and then traverse through the entire list. Every element in the list is visited, therefore the answer is "b) O(n)".
2) To find the last node of a linked list with a pointer to that node is the most efficient procedure possible. It does not matter how many elements are in the list, one can jump directly to the node. Therefore the answer is "a) O(1)".
3) The best case scenario is that the first element is the one we are looking for. So only one step is necessary and the first part is O(1). The standard code for traversing a matrix is two for loops. If each for loop must go through all of its loops, then the answer will be O(n x n) or O(n^2). Therefore the answer is "c) O(1) : O(n^2)".
4) A full binary tree is one that has the last row of nodes completely filled, or has 2^r nodes where r is the row number starting with the first row being n = 1. Binary trees are one of the the most efficient searches. Even the worst case scenario is better than many others. Every time one moves from a parent to a child, he/she effectively eliminates half of the remaining tree from his/her search. Therefore the answer is "b) O(log (2^n - 1))". The minus one is because there is only one root.
How is this related in any way to this class or discussion 5?
The professor went over BigO briefly in class on Friday. Realized that I made an error on question 4, fixed it.
Links to this Page
Michael Gorbsky last edited on 9 December 2005 at 8:05 am by lawn-199-77-214-24.lawn.gatech.edu
Fall 2005 Discussion 5 last edited on 11 December 2005 at 7:39 pm by r44h79.res.gatech.edu
