Order of O Notation
Steven Alvarez
Ranch Hand
Posts: 66
posted 8 years ago
Hey guys, I'm trying to figure out the answer to these Order questions. I tried to answer a few, can you tell me if they are wrong/right and if wrong what the right answer would be? Thanks.
Here are the questions
Ok here are my guesses.
1. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
2. O(n) ???
3. O(n) ???
4. O(n) ???
5. Constant O(1)
6. Constant O(1)
7. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
8. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
9. Constant O(1)
10. Constant O(1)
How did I do? Can you help me with the ones I got wrong? Thanks.
Here are the questions
What is the order of each of the following tasks in the worst case?
1. Computing the sum of the first n even integers by using a for loop?
2. Displaying all n integers in an array
3. Displaying n integers in a sorted linked list
4. Displaying all n names in a circular linked list
5. Displaying one array element
6. Displaying the last integer in a linked list
7. Searching an array of n integers for a particular value by using a binary search
8. Sorting an array of of n integers into descending order by using a mergesort
9. Adding an item to a stack on n items
10. Adding an item to a queue of n items
Ok here are my guesses.
1. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
2. O(n) ???
3. O(n) ???
4. O(n) ???
5. Constant O(1)
6. Constant O(1)
7. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
8. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
9. Constant O(1)
10. Constant O(1)
How did I do? Can you help me with the ones I got wrong? Thanks.
posted 8 years ago
If my memory serves, this one should be O(n log n).
8. Sorting an array of of n integers into descending order by using a mergesort
8. You would begin with O(n/2) but since 1/2 is a constant its just O(n)
If my memory serves, this one should be O(n log n).
Alberto Caraz
Greenhorn
Posts: 18
posted 8 years ago
Yep, this is true.
Originally posted by Alberto Caraz:
I'm not sure about the wording of 7. By saying you're using binary search, I'm assuming that the array is already sorted. If that's the case, the absolute worst case is O(ln n). Otherwise, it will take O(n ln n) peprocessing time to sort them.
Yep, this is true.
Hug your destiny! And hug this tiny ad:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
