Determining Big O Notation

An easier way

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4

53 Replies - 149868 Views - Last Post: 02 March 2013 - 05:43 PM Rate Topic: -----

#31 amtrbz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 05-February 11

Re: Determining Big O Notation

Posted 05 February 2011 - 11:09 PM

Hi, Thanks for such a great tutorial, i am still having some trouble understanding how to figure out a big O by just looking at a code. Can you explain me using few of the example problems..

************************************************************
    for (int i=0; i<numItems; i++)
       System.out.println(i+1);


************************************************************
  
    for (int i=0; i<numItems; i++)
       for (int j=0; j<numItems; j++)
          System.out.println( (i+1) * (j+1) );



************************************************************
   
    for (int i=0; i<numItems+1; i++)
       for (int j=0; j<2*numItems; j++)
          System.out.println( (i+1) * (j+1) );



************************************************************
    if ( num < numItems )
       for (int i=0; i<numItems; i++)
       {
          System.out.println(i);  
       }
    else
       System.out.println("too many");


************************************************************
     int i = numItems;
     while (i > 0)
        i = i / 2;


************************************************************
     public static int div(int num)
     {
        if (num == 0)
           return 0;
        else
           return num%2 + div(num/2);
     }


Was This Post Helpful? 0
  • +
  • -

#32 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 13 February 2011 - 06:07 PM

The first one is O(n) where n = numItems.

Use this as a reference for the rest.
Was This Post Helpful? 0
  • +
  • -

#33 Guest_amtrbz*


Reputation:

Re: Determining Big O Notation

Posted 14 February 2011 - 12:23 PM

View PostKYA, on 13 February 2011 - 06:07 PM, said:

The first one is O(n) where n = numItems.

Use this as a reference for the rest.



Thanks...
Was This Post Helpful? 0

#34 amtrbz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 05-February 11

Re: Determining Big O Notation

Posted 20 February 2011 - 09:52 PM

I'm trying to find the Big O for each of these code fragments, for an ArrayList and a Linked List:

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;
      }


I think it is O(N) for an arrayList and O(N^3) for a linked list; though I am unsure if both calls to lst.get in the else loop count as O(N) each.



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


Since there is an enhanced for loop, which efficiently moves from one item to the next, I think it is O(N^2) for an arryList and O(N) for a linked list.


public static int Count( List<Integer> lst1, List<Integer> lst2)
   {
      Iterator<Integer> itr1 = lst1.iterator();

      int count=0;
      while ( itr1.hasNext() )            //O(N)
      {
         Integer x = itr1.next();
         Iterator<Integer> itr2 = lst2.iterator();
         while ( itr2.hasNext() )
            if ( x.equals( itr2.next()) )
               count++;
      }

      return count;
   }



I am confused about the hasNext function; I assume that for array and linkedList, the running time is O(N^2) because of the two nested while loops.

This post has been edited by amtrbz: 20 February 2011 - 09:53 PM

Was This Post Helpful? 0
  • +
  • -

#35 gbk  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 22-March 11

Re: Determining Big O Notation

Posted 28 March 2011 - 02:25 PM

Thank you so much for this post it helped me a lot but i have a question :
the big O for linked list is n and for the binary search tree is nlogn
i want to know how that answer came up !!!
Was This Post Helpful? 0
  • +
  • -

#36 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 21
  • Joined: 31-March 11

Re: Determining Big O Notation

Posted 04 April 2011 - 09:31 AM

for ( int j = 0; j < 2*n; j++){
for ( int k = 0; k < n * n * n; k += 3)
sum++;
}



what will be the detailed running time analysis and then write down the final answer in Big-O notation
Was This Post Helpful? 0
  • +
  • -

#37 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10781
  • View blog
  • Posts: 40,153
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 04 April 2011 - 09:36 AM

I answered your question in your thread here.
Was This Post Helpful? 0
  • +
  • -

#38 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 21
  • Joined: 31-March 11

Re: Determining Big O Notation

Posted 04 April 2011 - 09:38 AM

running time analysis and then write down the final answer in Big-O notation:

for ( int j = 0; j < 2*n; j++){
for ( int k = 0; k < n * n * n; k += 3)
sum++;
}


Was This Post Helpful? -1
  • +
  • -

#39 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 21
  • Joined: 31-March 11

Re: Determining Big O Notation

Posted 04 April 2011 - 10:34 PM

what will be the big oh notation for these?
1.
for(i=0; i<=n;i+2)
for(j=0; j<=n; j+2)
s;



2.
for(i=1; i<=n; i++)
for(j=i; j<=a; j++)
s;



According to me-
1. outer loop- n
inner loop- n
for 'S' - i do not know.

Big oh notation should be O(n^2)

2.
outer loop- n+1
inner loop- dnt knw
for 'S'- dnt knw

big oh notation- ???
Was This Post Helpful? 0
  • +
  • -

#40 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 21
  • Joined: 31-March 11

Re: Determining Big O Notation

Posted 05 April 2011 - 04:51 PM

I have posted my problem 3 times and it has been deleted everytime I post it. I even provided the answer. just need help to see if im right or wrong.
Please dnt delete my post again cz i really need help.

1. for(i=0;i<=n;i+2)
           for(j=0;j<=n;J+2)
                s;
      2. for (i=1; i<=n;i++)
              for(j=i; j<=a; j++)
                 s;
where a is a constant value>1



1. outer loop 2n+1
inner loop n(2n+2)
for 's' n

big oh notation- O(n^2)

2. outer loop 2n+2
inner loop n(2n+2)
for 's' n

big oh notation 'dont knw'

Im having trouble understanding big oh notation and explaining runnint time analysis for each line. Kindly help me out.
Was This Post Helpful? -1
  • +
  • -

#41 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10781
  • View blog
  • Posts: 40,153
  • Joined: 27-December 08

Re: Determining Big O Notation

Posted 05 April 2011 - 05:03 PM

The reason your other threads were closed was because you were duplicate posting! Stop it!!!

As for the Big-O's, you can assume s is constant-time, and therefore negligible b/c you don't have enough information to determine otherwise.

For problem one:
-You are correct on the outer loop: it is O(n)
-The inner loop is n/2, which comes out to O(n)
-n*n = n^2 --> O(n^2)

For problem 2, the inner loop is worst case O(n^2) because it takes (n-1) + (n-2) + (n-3) + ... + (n-a) time. As long as a = n-1, then it's O(n^2). If a < n-1, then you are closing in on O(an) instead.
Was This Post Helpful? 0
  • +
  • -

#42 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 21
  • Joined: 31-March 11

Re: Determining Big O Notation

Posted 05 April 2011 - 05:06 PM

i am sorry for violating the rules. i was not aware of it. :(
and thank u so mch for responding.
Was This Post Helpful? 0
  • +
  • -

#43 KaleXp  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 27-May 11

Re: Determining Big O Notation

Posted 28 May 2011 - 02:07 AM

first Of all I wanna Thank You Alot For YOur Great explanatioN of Big O notation ,, I was Only Nobing My head AND saying Yes to My instructor aT college i wasnot get So much..! but when a friend Referd me here To read this I reallY got it with out Facing difficulty..!! thanks KYA..!
but I hve only one question Dose The Effeciency Changes according To binary Or linear search i mean would it any diffrence For finding the efficieny Of a binary search or it will Be just Same ..!!
Appriciate Your Answers...
thanks
kale.J
Was This Post Helpful? 0
  • +
  • -

#44 ladyinblack  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 9
  • View blog
  • Posts: 419
  • Joined: 08-April 09

Re: Determining Big O Notation

Posted 24 July 2011 - 04:16 AM

Hey KYA,

Great tutorial. Certainly a quick look to brush up on forgotten information for me. Quick question, I am in my 3rd year of studies and doing AI, which mentions Complexity Analysis as well as O() notation. I remember complexity analysis in the day of my data structures studies, along with big O, but I don't remember exactly what it was again. Is complexity analysis any different from Big O? Is it the Analysis of Algorithms?

R
Was This Post Helpful? 0
  • +
  • -

#45 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

Re: Determining Big O Notation

Posted 30 July 2011 - 02:02 PM

View PostKaleXp, on 28 May 2011 - 03:07 AM, said:

first Of all I wanna Thank You Alot For YOur Great explanatioN of Big O notation ,, I was Only Nobing My head AND saying Yes to My instructor aT college i wasnot get So much..! but when a friend Referd me here To read this I reallY got it with out Facing difficulty..!! thanks KYA..!
but I hve only one question Dose The Effeciency Changes according To binary Or linear search i mean would it any diffrence For finding the efficieny Of a binary search or it will Be just Same ..!!
Appriciate Your Answers...
thanks
kale.J


Binary search will always be more efficient ten a linear search if the data is sorted.

View Postladyinblack, on 24 July 2011 - 05:16 AM, said:

Hey KYA,

Great tutorial. Certainly a quick look to brush up on forgotten information for me. Quick question, I am in my 3rd year of studies and doing AI, which mentions Complexity Analysis as well as O() notation. I remember complexity analysis in the day of my data structures studies, along with big O, but I don't remember exactly what it was again. Is complexity analysis any different from Big O? Is it the Analysis of Algorithms?

R


The terms can be interchangeable. You can use other tools in complexity analysis though. So Big O is a part of complexity analysis, but complexity analysis/analysis of algorithms does not always mean using Big O.
Was This Post Helpful? 1
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4