# Big-O Notation of a nested For and While loop

Page 1 of 1

## 7 Replies - 18548 Views - Last Post: 20 May 2014 - 12:33 PM

Reputation: 0
• Posts: 4
• Joined: 20-May 14

# Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 11:58 AM

Hey guys

I'm having trouble figuring out the Big-O notation for this loop.
For now I only have it in pseudocode. I hope you understand it anyway

```for i = 1 to n do
j = 1
while j <= n/2 do
print "*"
j = j + 1
end while
end for
```

Any help would be very helpful.
Is This A Good Question/Topic? 0

## Replies To: Big-O Notation of a nested For and While loop

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:14 PM

Moved to Computer Science.

I have a tutorial on Big-O as does KYA here. I ask that you review these tutorials and show us your good faith efforts. You will learn more this way than by us giving you an answer.

Reputation: 0
• Posts: 4
• Joined: 20-May 14

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:18 PM

thanks, I already tried to use KYA, but didn't help much.
I will try yours though.

macosxnerd101, on 20 May 2014 - 12:14 PM, said:

Moved to Computer Science.

I have a tutorial on Big-O as does KYA here. I ask that you review these tutorials and show us your good faith efforts. You will learn more this way than by us giving you an answer.

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:22 PM

You could rewrite the inner while loop as a for loop:
```for j = 1 to n/2 do:

```

With nested loops, KYA's tutorial tells us to multiply their asymptotic complexities. What is the complexity of the outer loop? What is the complexity of the inner loop?

Reputation: 0
• Posts: 4
• Joined: 20-May 14

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:24 PM

Reading your tutorial ( @macosxnerd101 ) still explain probably to me why the result is O(n^2).
As far as I can tell line 3:
``` while j <= n/2 do
```

is log(n)

and since it is nested and the For loop is (n) I would say the answer should be O(n*log(n)??

macosxnerd101, on 20 May 2014 - 12:14 PM, said:

Moved to Computer Science.

I have a tutorial on Big-O as does KYA here. I ask that you review these tutorials and show us your good faith efforts. You will learn more this way than by us giving you an answer.

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:25 PM

Why is the while loop O(log(n))? Isn't it n/2? So what is n * n/2?

Reputation: 0
• Posts: 4
• Joined: 20-May 14

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:31 PM

I was just told that n/2 results in log(n)??

So should it be like:

For loop is (n)
While loop is (n/2)

And due to they are nested it is n*(n/2)
And that gives O(n*n)?

macosxnerd101, on 20 May 2014 - 12:25 PM, said:

Why is the while loop O(log(n))? Isn't it n/2? So what is n * n/2?

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Big-O Notation of a nested For and While loop

Posted 20 May 2014 - 12:33 PM

If you divide by 2 on each iteration, then you are correct. But the variable being modified is j, not n.

So this is log(n):
```for(int i = 1; i < n; n = n/2)

```

While this is n/2 = O(n):
```for(int i = 0; i < n/2; i++)

```