This week's giveaway is in the EJB and other Java EE Technologies forum.
We're giving away four copies of EJB 3 in Action and have Debu Panda, Reza Rahman, Ryan Cuprak, and Michael Remijan on-line!
See this thread for details.
The moose likes Java in General and the fly likes Order of O Notation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Order of O Notation" Watch "Order of O Notation" New topic
Author

Order of O Notation

Steven Alvarez
Ranch Hand

Joined: Nov 01, 2006
Posts: 66
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

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.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18113
    
  39


6. Displaying the last integer in a linked list

6. Constant O(1)


Depends on the linked list implementation. If the linked list has a tail pointer, then it is O(1). Otherwise, it is O(n).


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18113
    
  39


7. Searching an array of n integers for a particular value by using a binary search

7. You would begin with O(n/2) but since 1/2 is a constant its just O(n)


Only in the worst case. In the average case, it is O(log n).
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18113
    
  39

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).
Steven Alvarez
Ranch Hand

Joined: Nov 01, 2006
Posts: 66
2,3,4 correct? thanks.
Steven Alvarez
Ranch Hand

Joined: Nov 01, 2006
Posts: 66
anyone?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24166
    
  30

Yes, all the other ones are right (IMO).


[Jess in Action][AskingGoodQuestions]
Alberto Caraz
Greenhorn

Joined: Apr 27, 2007
Posts: 18
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.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24166
    
  30

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.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18113
    
  39

Good point. I totally missed "array" in the description -- and just assumed some sort of unbalanced binary tree.

Henry
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Order of O Notation
 
Similar Threads
Help with Arrays!
Big O
Sun Cirtification
How can a Class create an instance of itself??
Comparing Array Elements