Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Complexity of this simple algorithm

 
Ranch Hand
Posts: 53
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76492
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76492
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 76492
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is what I thought you meant. Assuming all the loops run n×, n².
 
Hug your destiny! And hug this tiny ad:
The trailboss has a kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic