# Determining Big O Notation

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

## 53 Replies - 133858 Views - Last Post: 02 March 2013 - 05:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=125427&amp;s=0763cf5fb42a969f10bc21dbd6eefefa&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #31 amtrbz

• New D.I.C Head

Reputation: 0
• 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);
}

```

### #32 KYA

• g++ jameson.cpp -o beverage

Reputation: 3101
• Posts: 19,141
• 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.

Reputation:

## Re: Determining Big O Notation

Posted 14 February 2011 - 12:23 PM

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

### #34 amtrbz

• New D.I.C Head

Reputation: 0
• 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 )
}

```

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

### #35 gbk

• New D.I.C Head

Reputation: 0
• 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 !!!

### #36 goonjv

• New D.I.C Head

Reputation: -3
• 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

### #37 macosxnerd101

• Self-Trained Economist

Reputation: 10572
• Posts: 39,143
• Joined: 27-December 08

## Re: Determining Big O Notation

Posted 04 April 2011 - 09:36 AM

### #38 goonjv

• New D.I.C Head

Reputation: -3
• 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++;
}

```

### #39 goonjv

• New D.I.C Head

Reputation: -3
• 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- ???

### #40 goonjv

• New D.I.C Head

Reputation: -3
• 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.

### #41 macosxnerd101

• Self-Trained Economist

Reputation: 10572
• Posts: 39,143
• 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.

### #42 goonjv

• New D.I.C Head

Reputation: -3
• 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.

### #43 KaleXp

• New D.I.C Head

Reputation: 0
• 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 ..!!
thanks
kale.J

• D.I.C Regular

Reputation: 9
• 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

### #45 KYA

• g++ jameson.cpp -o beverage

Reputation: 3101
• Posts: 19,141
• Joined: 14-September 07

## Re: Determining Big O Notation

Posted 30 July 2011 - 02:02 PM

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