[amtrbz]

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

[KYA]

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

Use this as a reference for the rest.

[amtrbz]

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

[gbk]

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 !!!

[goonjv]

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

[macosxnerd101]

I answered your question in your thread here.

[goonjv]

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

[goonjv]

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- ???

[goonjv]

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.

[macosxnerd101]

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.

[goonjv]

i am sorry for violating the rules. i was not aware of it.
and thank u so mch for responding.

[KaleXp]

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

[ladyinblack]

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

[KYA]

KaleXp, 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.

ladyinblack, 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.