6 Replies - 404 Views - Last Post: 25 September 2011 - 09:57 AM Rate Topic: -----

#1 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Analyzing big-0

Posted 24 September 2011 - 07:57 PM

What will be the Big-o running itme if we pass:

a) arraylist
2) linked list
in the following method:

		   
         while(iterator.hasNext())
         {
              stack.push(iterator.next());   //O(1) for both snce push take constant time
              iterator.remove();             // O(1) for both since we are using iterator's remove
             
		}
        
         while(!stack.empty()) 
        { 
             list.add(stack.pop());		// O(1) for both since we are adding at the end of the list
        } 
  
       System.out.println(list);
  } 





Since the loops run n time. The running time is O(n) for both.

pleas ele tme know if am right

Is This A Good Question/Topic? 0
  • +

Replies To: Analyzing big-0

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Analyzing big-0

Posted 24 September 2011 - 08:46 PM

System.nanoTime()

http://download.orac...html#nanoTime()

returns the time in nano

just call it before and after your loop
You will have to have a huge amount of data in your stack to see a difference
Was This Post Helpful? 0
  • +
  • -

#3 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Analyzing big-0

Posted 24 September 2011 - 09:30 PM

All modifying operations (at the least the ones your using) for Java Collections run in constant time, so the code is of the order O(N).
Was This Post Helpful? 1
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Analyzing big-0

Posted 24 September 2011 - 09:47 PM

You are kind of right
Their should not be a difference between Stack.add() and Vector.add()
A Stack is just a Vector to which the pop() method returns the last element of the list

Actually the Stack.java source code contains a lot more comments that actual code :)

/*
 * %W% %E%
 *
 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @version %I%, %G%
 * @since   JDK1.0
 */
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
	addElement(item);

	return item;
    }

    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return     The object at the top of this stack (the last item
     *             of the <tt>Vector</tt> object).
     * @exception  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
	E	obj;
	int	len = size();

	obj = peek();
	removeElementAt(len - 1);

	return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return     the object at the top of this stack (the last item
     *             of the <tt>Vector</tt> object).
     * @exception  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
	int	len = size();

	if (len == 0)
	    throw new EmptyStackException();
	return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
	return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
	int i = lastIndexOf(o);

	if (i >= 0) {
	    return size() - i;
	}
	return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}


Was This Post Helpful? 1
  • +
  • -

#5 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2101
  • View blog
  • Posts: 3,203
  • Joined: 21-June 11

Re: Analyzing big-0

Posted 25 September 2011 - 03:33 AM

Are we talking LinkedList vs. ArrayList for the stack or for the collection being iterated over? Because while push and pop are indeed O(1)¹ no matter whether you use an ArrayList or a LinkedList, the same is not true for Iterator.remove, which is O(n) for array lists.

So if iterator is an iterator of an ArrayList, the runtime of your code will be quadratic.

¹ Well, amortized O(1) for ArrayLists.
Was This Post Helpful? 1
  • +
  • -

#6 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Analyzing big-0

Posted 25 September 2011 - 07:55 AM

@sep2kk,you are damn right....thanx...And thanx to all for your inputs
Was This Post Helpful? 0
  • +
  • -

#7 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Analyzing big-0

Posted 25 September 2011 - 09:57 AM

Iterator.remove is O(N). I mistakenly assumed the remove method could be done in constant time. Here's the implementation from DocJar:

public E remove(int index) {
  445           rangeCheck(index);
  446   
  447           modCount++;
  448           E oldValue = elementData(index);
  449   
  450           int numMoved = size - index - 1;
  451           if (numMoved > 0)
  452               System.arraycopy(elementData, index+1, elementData, index,
  453                                numMoved);
  454           elementData[--size] = null; // Let gc do its work
  455   
  456           return oldValue;
  457       }



So using ArrayLists your code would be O(N^2) and for LinkedLists O(N).
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1