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.

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

Any help would be very helpful.

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.

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.

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.

Posted 20 May 2014 - 12:18 PM

thanks, I already tried to use KYA, but didn't help much.

I will try yours though.

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.

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.

Posted 20 May 2014 - 12:22 PM

You could rewrite the inner while loop as a for loop:

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?

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?

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:

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.

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.

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.

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.

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?

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):

While this is n/2 = O(n):

And your reasoning about O(n^{2}) is correct.

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(n

Page 1 of 1

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- Python
- PHP
- Mobile Development
- ASP.NET
- .NET Framework
- Ruby
- Game Development
- Assembly
- Databases
- ColdFusion
- VB6
- Other Languages
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- C++ Tutorials
- Java Tutorials
- VisualBasic Tutorials
- VB.NET Tutorials
- C# Tutorials
- PHP Tutorials
- ColdFusion Tutorials
- Database Tutorials

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2018 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3