11 Replies - 453 Views - Last Post: 22 June 2013 - 07:38 PM Rate Topic: -----

#1 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

whats the big O running time in the following code?

Posted 22 June 2013 - 03:52 PM

public static int calc( List<Integer> lst )
      {
         int count = 0;
         int N = lst.size();

         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.
b. If a LinkedList is passed.

This post has been edited by macosxnerd101: 22 June 2013 - 04:46 PM
Reason for edit:: Please use code tags

Is This A Good Question/Topic? 0
  • +

Replies To: whats the big O running time in the following code?

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 04:47 PM

What have you tried? Show us your efforts and we'll be happy to help. Please don't just dump your homework though.
Was This Post Helpful? 0
  • +
  • -

#3 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 06:29 PM

public static void erase( List<Integer> lst )
   {
      Iterator<Integer> itr = lst.iterator();

      while ( itr.hasNext() )
      {
         Integer x = itr.next();
         itr.remove();
      }

   }


a. If an ArrayList is passed for lst1 and lst2.
b. If a LinkedList is passed for lst1 and lst2.
I'm sorry this one the right code one , I am thinking for the first part a is O(n) and for the second one O(n^2) because the iteratation is from n*n in the second one but not in the first one,,please any help

This post has been edited by macosxnerd101: 22 June 2013 - 06:30 PM
Reason for edit:: Use code tags

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 06:33 PM

Again, please use code tags: :code:.

For the calc() method, that is correct. For erase, it is Theta(n) for both ArrayList and LinkedList objects, based on the Iterator implementations. The Iterator next() method for LinkedList (and ArrayList) provides Theta(1) lookup time to get the next element.
Was This Post Helpful? 0
  • +
  • -

#5 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 06:58 PM

public static void add( List<Integer> lst1, List<Integer> lst2)
   {
      for ( Integer x : lst1 )
         lst2.add(0, x);        // add to front
   }


what about this one , I am getting O(n) on both of them, correct me if am wrong thank you

This post has been edited by macosxnerd101: 22 June 2013 - 07:07 PM
Reason for edit:: Please use code tags

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:08 PM

This is the third time I've had to add code tags. Please use them: :code:. Consider this a formal warning.

Your analysis is correct.
Was This Post Helpful? 0
  • +
  • -

#7 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:18 PM

public static void add( List<Integer> lst1, List<Integer> lst2)
   {
      for ( Integer x : lst1 )
         lst2.add(0, x);        // add to front
   }


I am getting O(n^2) for Arraylist and O(n) for linklist am i right or wrong?

I am so sorry about that I will use code tags , I am sorry i meant to say I got O(n^2) for arraylist and O(n) for linklist am i wrong or right?

This post has been edited by macosxnerd101: 22 June 2013 - 07:21 PM
Reason for edit:: CODE TAGS! USE THEM!

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:22 PM

You're STILL not using code tags. Seriously, it's not that hard, and instructions are *everywhere* on the site. Please learn to read the instructions and use code tags.
Was This Post Helpful? 0
  • +
  • -

#9 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:31 PM

Sorry, just tell if am right or wrong with O(n^2) for arraylist and O(n) for linklist. thank I will appreciate it
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:34 PM

You're on the right track.

Please be advised though- I'm going to close the thread if you post another code sample without using code tags. You've been around since November. Code tags are not that hard to figure out.
Was This Post Helpful? 0
  • +
  • -

#11 rogjava  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 16
  • Joined: 20-November 12

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:37 PM

Sorry, just tell if am right or wrong with O(n^2) for arraylist and O(n) for linklist. thank I will appreciate it . I am not adding anycode anymore its just from the previous one. I will do it I appologize. but, tell if for arraylist am getting O(n^2) and for linklist O(n) is this correct?
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10470
  • View blog
  • Posts: 38,809
  • Joined: 27-December 08

Re: whats the big O running time in the following code?

Posted 22 June 2013 - 07:38 PM

I already answered your question in my last post.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1