I have a function that rearranges an input list in a certain way and returns the output list. I am confused about what the time and space complexity of the function will be. Below is the code:

def rearrange_list(inp_list):
    d = {}
    output_list = []
    for num in inp_list:
        if num in d:
            d[num]  = 1
        else:
            d[num] = 0
            output_list.append(num)
    for k,v in d.items():
        if v > 0:
            for i in range(v):
                output_list.append(k)
    return output_list

This is my complexity analysis:

• Time complexity: O(n m²) where n is length of the input list and m is the size of dictionary
• Space complexity: O(n) where n is the length of input list

The main confusion I have is should I consider iterating through the dictionary O(n) too since worst case we will have n items in the list, or should it be represent it by m like I did in my analysis since it can be anything from 0 to n?

Thank you in advance for your help!

CodePudding user response：

Do a step by step breakdown of the algorithm:

1. First for loop (for num in inp_list).
   It simply iterates over the list, which takes O(N) time, and the dictionary has size O(number of unique elements in list), which can be generalized as O(N) space (where N = length of list = max possible number of unique keys).
2. Second for loop (for k,v in d.items()).
   This iterates over the keys in dict, which are O(number of unique elements in list) in count.
3. Third for loop (for i in range(v)).
   Since summation of v would just be the count of duplicate elements in the list, it will have an upper bound of O(N).

A better approximation of the algorithm should be O(N) time and space, rather than the proposed O(n m^2)

CodePudding user response：

Your time and space complexity are both Theta(n). While sometimes it can be useful for clarity to include terms in the time or space complexity that don't change the asymptotic value (a classic example being string searching algorithms), it doesn't make as much sense here.

While your claim of O(n m^2) time complexity is technically correct as Big-O notation is an upper bound, you can show that O(n) is also an upper bound, since the dictionary has size at most n and we iterate over each key exactly once: there are n items read from input, at most n loop iterations for the dictionary, and n items appended to the output list.

If you wanted, you can calculate 'auxiliary' space required, which would be the amount of space needed but not counting the input or output arrays. Here, that would be Theta(m). You should note, however, that such analyses are fairly uncommon: by assumption, unless specified otherwise, space complexity analysis will include the size of the output.

CodePudding user response：

Time complexity

You can divide the code into two parts.

Part 1

for num in inp_list:
    if num in d:
        d[num]  = 1
    else:
        d[num] = 0
        output_list.append(num)

In the first line you iterate through inp_list, and in each iteration you call if num in d. What python does is searches through the keys of dictionary d, therefore the time complexity for this part is O(nm) where n is the size of inp_list and m is the size the number of unique values in inp_list.

Part 2

for k,v in d.items():
    if v > 0:
        for i in range(v):
            output_list.append(k)

In this part you iterate through the size of the dictionary in the first row which is O(m). I am ignoring the nested for loop since the loop can be replaced by the following:

output_list = output_list   [k] * v

Which happens in O(1)

In conclusion, the time complexity should be O(nm m) = O (m(n 1)) = O(nm).

Nevertheless, since d is a dictionary, the key search takes O(1) instead of O(m) (see more here), making the time complexity drop to O(n).

Space complexity

Since a dictionary with m keys is created (where m is the number of unique values in inp_list, the space complexity is O(n m) < O(2n) = O(n)

Suggestions

There is a way to drastically increase the runtime of the code without changing the complexity for large inp_list. In your code you keep appending, thus each time you append python need to re-allocate memory for the array. This can be cancelled by pre-allocating memory at the beginning and inserting the values in their right place