If time complexity of pop (first item) is O(n) and the time complexity for a set slice is O(k), why is my slicing function so slow? /u/justalemontree Python Education

Hi, I’m a beginner who has just started an introductory algorithm course. I’ve just finished the part on list operations and was playing around measuring runtime of each operation. I’ve written a function that adds consecutive numbers to the end of a list (from 1, 2, 3… to n), and other functions that remove the first or last number in that list.

Appending and popping numbers at the end of the list runs in O(1) time so it’s blazing fast.

Popping the first number runs in O(n) time, so it’s a bit slower.

To my surprise slicing from [1:] was extremely slow, but I thought slicing runs in O(k) time (in this case k is just n-1 so they should be similar)?

Is it the way that I’ve coded the function that made it slow? Is it the repeated variable assignment that slowed it down this much? Or is my time complexity analysis wrong? Thanks!

(I do realize that I’m running each list operation n times, so the time complexities of the functions are n times the time complexity of the operation, but my question remains)

import time def add_last_num(num_list, times): for i in range (1, times+1): num_list.append(i) def pop_last_num(num_list, times): for i in range (times): num_list.pop() def pop_first_num(num_list, times): for i in range(times): num_list.pop(0) def slice_first_num(num_list, times): for i in range(times): num_list = num_list[1:] return num_list nums = [] n = 10**5 start = time.time() add_last_num(nums, n) end1 = time.time() pop_last_num(nums, n) end2 = time.time() add_last_num(nums, n) end3 = time.time() pop_first_num(nums, n) end4 = time.time() add_last_num(nums, n) end5 = time.time() nums = slice_first_num(nums, n) end6 = time.time() print(f"add_last_num took {end1 - start} seconds") # runtime = 0.0015 seconds print(f"pop_last_num took {end2 - end1} seconds") # runtime = 0.0019 seconds print(f"pop_first_num took {end4 - end3} seconds") # runtime = 0.6272 seconds print(f"slice_first_num took {end6 - end5} seconds") # runtime = 9.6040 seconds!! 

Hi, I’m a beginner who has just started an introductory algorithm course. I’ve just finished the part on list operations and was playing around measuring runtime of each operation. I’ve written a function that adds consecutive numbers to the end of a list (from 1, 2, 3… to n), and other functions that remove the first or last number in that list.

Appending and popping numbers at the end of the list runs in O(1) time so it’s blazing fast.

Popping the first number runs in O(n) time, so it’s a bit slower.

To my surprise slicing from [1:] was extremely slow, but I thought slicing runs in O(k) time (in this case k is just n-1 so they should be similar)?

Is it the way that I’ve coded the function that made it slow? Is it the repeated variable assignment that slowed it down this much? Or is my time complexity analysis wrong? Thanks!

(I do realize that I’m running each list operation n times, so the time complexities of the functions are n times the time complexity of the operation, but my question remains)

import time def add_last_num(num_list, times): for i in range (1, times+1): num_list.append(i) def pop_last_num(num_list, times): for i in range (times): num_list.pop() def pop_first_num(num_list, times): for i in range(times): num_list.pop(0) def slice_first_num(num_list, times): for i in range(times): num_list = num_list[1:] return num_list nums = [] n = 10**5 start = time.time() add_last_num(nums, n) end1 = time.time() pop_last_num(nums, n) end2 = time.time() add_last_num(nums, n) end3 = time.time() pop_first_num(nums, n) end4 = time.time() add_last_num(nums, n) end5 = time.time() nums = slice_first_num(nums, n) end6 = time.time() print(f"add_last_num took {end1 - start} seconds") # runtime = 0.0015 seconds print(f"pop_last_num took {end2 - end1} seconds") # runtime = 0.0019 seconds print(f"pop_first_num took {end4 - end3} seconds") # runtime = 0.6272 seconds print(f"slice_first_num took {end6 - end5} seconds") # runtime = 9.6040 seconds!!