This project demonstrates asymptotic time of list operations in Scratch. Graps (clockwise, from left-top): 1) y = time needed to create list of size x using "add to list" block. 2) y = time needed to access 1024 random elements in list of size x. 3) y = time needed to delete 128 random elements from list of size x 4) y = time needed to create list of size x using "insert at .." block We can see that n calls of "add to list" takes linear time so one "add to list" takes amortized constant. List reallocates from size to size + const, as we can see from the first graph. Random access is a very strange graph, because on my computer it is linear from beginning, but then it becomes constant. So random access is O(1) time. Erase graph is scattered, but we can see that erase of random element takes O(n) time. "Insert at" graph is the most interesting one. It looks like "insert at 1" should take O(n) time, to demonstrate it we will draw graph with points (size, time / size). It is linear. So, one "insert at 1" call takes O(n) time! Let's find data structure with the following asymptotic time: add element to back -- O(1), get random element -- O(1), erase random element -- O(n), insert at random position -- O(n). This is a dynamic array -- std::vector in C++, for example. So name "list" is misleading, because list in computer science has O(n) random access time and O(1) insert at first position, for example.
https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Amortized_analysis https://en.wikipedia.org/wiki/Dynamic_array
