You are Here: Home

# Running time question Watch

1. OK this has been bugging () me lately, but is there a way to list all k-tuples of a list in a time complexity faster than O(nk)? I'm asking because I've encountered several coding problems that require this faster algorithm to score highly in performance
2. (Original post by shawn_o1)
OK this has been bugging () me lately, but is there a way to list all k-tuples of a list in a time complexity faster than O(nk)? I'm asking because I've encountered several coding problems that require this faster algorithm to score highly in performance
Did you mean O(n2) not O(nk)? In that case wouldn't O(n * log(n)) be the fastest?
3. (Original post by Vyres)
Did you mean O(n2) not O(nk)? In that case wouldn't O(n * log(n)) be the fastest?
OK, an example would be: finding all (x, y, z) triplets from the natural numbers between 1 and 5 such that x < y < z. Which means, retrieving (1, 2, 3), (1, 2, 4), ... , (2, 4, 5), (3, 4, 5). Instead of making three nested loops iterating from 1 to 3, 2 to 4 and 3 to 5 respectively, which causes the inefficient O(n3) time, how do I use the O(n log n) algorithm you suggest?
4. (Original post by shawn_o1)
OK, an example would be: finding all (x, y, z) triplets from the natural numbers between 1 and 5 such that x < y < z. Which means, retrieving (1, 2, 3), (1, 2, 4), ... , (2, 4, 5), (3, 4, 5). Instead of making three nested loops iterating from 1 to 3, 2 to 4 and 3 to 5 respectively, which causes the inefficient O(n3) time, how do I use the O(n log n) algorithm you suggest?
Well for O(n * log(n))
Code:
```x = 1
while(x < n)
x = x * 2```
But I don't think this is useful for what you want, or is it?
5. (Original post by shawn_o1)
OK this has been bugging () me lately, but is there a way to list all k-tuples of a list in a time complexity faster than O(nk)? I'm asking because I've encountered several coding problems that require this faster algorithm to score highly in performance
I don't think so. If your result is going to be of size O(n^k) and you are creating the tuples and adding them to your result in constant time, that is a running time of O(n^k).

(Original post by shawn_o1)
OK, an example would be: finding all (x, y, z) triplets from the natural numbers between 1 and 5 such that x < y < z. Which means, retrieving (1, 2, 3), (1, 2, 4), ... , (2, 4, 5), (3, 4, 5). Instead of making three nested loops iterating from 1 to 3, 2 to 4 and 3 to 5 respectively, which causes the inefficient O(n3) time, how do I use the O(n log n) algorithm you suggest?
You would not hardcode the values in your loops. It would be 0 < i < 4, i < j < 5, j < k < 6, giving tuples (i, j, k). Your current values seem like they would allow the tuple (3,2,3), although they are the correct values that the ranges could take.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: September 4, 2016
Today on TSR

### Falling in love with him

But we haven't even met!

### Top study tips for over the Christmas holidays

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

Can you help? Study Help unanswered threadsStudy Help rules and posting guidelines

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.