Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Online

    21
    ReputationRep:
    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
    Offline

    2
    ReputationRep:
    (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?
    • Thread Starter
    Online

    21
    ReputationRep:
    (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?
    Offline

    2
    ReputationRep:
    (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?
    • PS Reviewer
    Offline

    16
    ReputationRep:
    PS Reviewer
    (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.
 
 
 
  • 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
    Would you like to hibernate through the winter months?
  • 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

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