This week's book giveaways are in the Angular and TypeScript and Web Services forums.
We're giving away four copies each of Programming with Types and The Design of Web APIs and have the authors on-line!
See this thread and this one for details.
Win a copy of Programming with Types this week in the Angular and TypeScript forum
or The Design of Web APIs in the Web Services forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Henry Wong
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Joe Ess
  • salvin francis

Complexity of this simple algorithm

 
Ranch Hand
Posts: 53
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've created a pseudo-code version of a problem I was given in an interview



Would I be right in saying the complexity is Order N squared or : O(n^2)

The first forLoop is run a constant amount of times so N doesn't change.
The second loop runs N times also, but since it calls a function which contains a third loop, Its essentially a nested loop N*N which is N squared ?

Finally, after writing an algorithm like this. How often do companies quiz you on the complexity of your loops etc. ?

 
Marshal
Posts: 66975
255
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Question maybe a bit scary for the “beginning” forum, so I think I shall move you.

You wouldn't pass “Array[]” to a method, but “Array”. Once you work that out, yes the whole code runs in quadratic complexity (=n²) as its upper limit. It might behave more like linear if the size of the array is very small, but complexity is calculated on a worst‑case basis, so it is correct ot say quadratic.
 
Kevin Mckeon
Ranch Hand
Posts: 53
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Question maybe a bit scary for the “beginning” forum, so I think I shall move you.

You wouldn't pass “Array[]” to a method, but “Array”. Once you work that out, yes the whole code runs in quadratic complexity (=n²) as its upper limit. It might behave more like linear if the size of the array is very small, but complexity is calculated on a worst‑case basis, so it is correct ot say quadratic.



So in that case, if you had 3 for loops nested, the complexity would be N cubed.

But what if you had 4 For loops in total, a nested loop at the beginning of the program and a different nested for loop at the end of the program.

Would the complexity still be N squared ? Or N^4 now ?
 
Campbell Ritchie
Marshal
Posts: 66975
255
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kevin Mckeon wrote:. . . if you had 3 for loops nested, the complexity would be N cubed.

Yes, n³ assuming they are all nested inside each other.

But what if you had 4 For loops in total, a nested loop at the beginning of the program and a different nested for loop at the end of the program . . .

If I understood the question properly, n²
 
Kevin Mckeon
Ranch Hand
Posts: 53
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:If I understood the question properly, n²



Sorry this is the scenario I mean

 
Campbell Ritchie
Marshal
Posts: 66975
255
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is what I thought you meant. Assuming all the loops run n×, n².
 
Message for you sir! I think it is a tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!