You are Here: Home

# Running time question

Announcements Posted on
TSR's new app is coming! Sign up here to try it first >> 17-10-2016
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.

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. Oops, you need to agree to our Ts&Cs to register

Updated: September 4, 2016
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:
Today on TSR

### How does exam reform affect you?

From GCSE to A level, it's all changing

Poll
Useful resources