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

#1 phha11ad   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12324
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 phha11ad   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.

View Postmacosxnerd101, 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.

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12324
  • View blog
  • 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?
Was This Post Helpful? 1
  • +
  • -

#5 phha11ad   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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)??

thanks for your help, and quick answer.

View Postmacosxnerd101, 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.

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12324
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#7 phha11ad   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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)?

View Postmacosxnerd101, 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?

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12324
  • View blog
  • 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++)



And your reasoning about O(n2) is correct.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1