Results 1 to 1 of 1

Math Help - Some Big-O problems

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Some Big-O problems

    I would really appreciate it if someone would verify that these solutions are correct, I am supposed to find the Big O of the code fragment:

    Code:
    public static int calc( List<Integer> lst, int N )
          {
             int count = 0;
             for ( int i=0; i<N; i++)
             {
                if (lst.get(i) > 0)
                   sum += lst.get(i);
                else
                   sum += lst.get(i) * lst.get(i);  
             }
             return sum;
          }
    a. If an ArrayList is passed. (get operations are O(1) for ArrayList)
    O(N^2)

    b. If a LinkedList is passed. (get operations are O(N) for LinkedList)
    O(N^4), confused by this one, because I do not know whether to count
    both 1st.get line in the else statements as O(N) and multiply; this is
    what I did.


    Next problem:
    Code:
    public static void add( List<Integer> lst1, List<Integer> lst2)
       {
          for ( Integer x : lst1 )
             lst2.add(0, x);
       }
    a. If an ArrayList is passed for lst1 and lst2.
    According to my book, an enhanced for loop makes the running time O(N) for any list, becuase the iterator will efficiently advance from one item to the next, so I assume this is O(N)?

    b. b. If a LinkedList is passed for lst1 and lst2.
    I presume the answer is the same as for part a, because it says O(N) running time for ANY list structure with an enhanced for loop.

    Last Problem: (Too big to put in code block format)

    public static int Count( List<Integer> lst1, List<Integer> lst2) {
    Iterator<Integer> itr1 = lst1.iterator();
    int count=0;
    while ( itr1.hasNext() ) {
    Integer x = itr1.next();
    Iterator<Integer> itr2 = lst2.iterator();
    while ( itr2.hasNext() )
    if ( x.equals( itr2.next()) )
    count++; }
    return count; }

    a. If an ArrayList is passed for lst1 and lst2. Explain your answer.
    b. If a LinkedList is passed for lst1 and lst2. Explain your answer.

    For both of these, I got O(N) for the first while loop times O(N) for the second while loop times O(N) for the if loop, for a total of O(N^3). I know this cannot be right, as there has to be more to the problem than this. Maybe the count operation takes O(N) for the arrayList instead of constant time because the array may shift?
    Last edited by aaronrj; February 3rd 2010 at 05:38 PM. Reason: didn't put code for last problem
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 3rd 2011, 06:35 AM
  2. binomial problems/normal problems
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 20th 2010, 12:46 AM
  3. binomial problems as normal problems
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 20th 2010, 12:41 AM
  4. Problems with integration word problems
    Posted in the Calculus Forum
    Replies: 5
    Last Post: April 25th 2010, 06:39 PM
  5. Help thease problems problems
    Posted in the Geometry Forum
    Replies: 2
    Last Post: April 1st 2008, 12:03 PM

Search Tags


/mathhelpforum @mathhelpforum