troubleshooting Question

Time complexity in nested for loop.

Avatar of krakatoa
krakatoaFlag for United Kingdom of Great Britain and Northern Ireland asked on
Java
13 Comments1 Solution33 ViewsLast Modified:

Any idea about what the time complexity would be for two nested for loops, where the inner loop works with a shrinking set  . . . more or less like this : 


int y = 0;
for(int t = 0;t<x;t++){
                     for(int i = 0;i<x-y;i++){                 // do something                             }             y++;             // some other small task }

It ought to be something less than quadratic, should it not ?

ASKER CERTIFIED SOLUTION
dpearson

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 1 Answer and 13 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 13 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros