1b

Answer: Start by comparing the first pair of elements and swap them if the first element is greater than the second (assuming ascending order). Repeat for all pairs in the list. Repeat this whole iteration n-1 times (or until the whole list is sorted by checking if no swaps were done in the current iteration (optimisation 1)). There is no need to check the elements that were already sorted in subsequent iterations so reduce the range by 1 in each iteration (optimisation 2).

Answer:

It is n-1 swaps! 🙂

Feedback: Would be good to define what n actually is

Alternate Answer:
n-1 swaps, where n is the number of elements in the list

Yeap this is correct

Answer:

The overall complexity of Bubble sort 1 in both best and worst cases is O(n^2)

The overall best-case complexity of Bubble sort 2 is O(n) and its worst case complexity is O(n^2) where n is the length of list.

Feedback: Would be good to define what n actually is for Bubble Sort 1:

The overall complexity of Bubble sort 1 in both best and worst cases is O(n^2), where n is the number of elements in the list

Answer:

Bubble sort 1 has two loops. The outer loop runs n-1 times and so does the inner loop (n is the length of the list). So the overall complexity in all cases comes out to be (n-1)^2 which is O(n^2).

Bubble sort 2 also has two loops but there is a conditional break. If none of the numbers are swapped during a traversal, then the loop is stopped. The best case of O(n) occurs when the list is already sorted and it takes one traversal to make sure that the list is sorted.

The worst case is when the list is sorted in the reverse order (both inner and outer loop will run n-1 times). So the worst case complexity is O(n^2).

Alternative Answer #1 (more in depth)
(Feedback: Correct)

• For the best case, this will occur when the list is already sorted

  • Bubble Sort II will check every element in the list once, resulting in n operations, where n is the number of elements in the list.

  • It will check only once since the "swapped" value will be true after one traversal of the list, making the algorithm exiting early.

  • This gives a time complexity of O(n), where n is the number of elements in the list

• For the worst case, this will occur when the list is in reverse order

  • The "swapped" variable will not break early.

  • The number of comparisons will be (n-1) + (n-2) + ... + 1, which simplifies to (n^2-n)/2, which results in O(n^2), where n is the number of elements in the list

Answer: [5,-5,10,3,20]

Answer: [-20,-5,-10,-5,3]

Answer:

Bubble sort 1 stops after n-1 iterations of the outer loop. Bubble sort 2 stops when none of the elements have been swapped in the last. Bubble sort 2 is the optimised version of bubble sort 1 where there is a conditional break if the list becomes sorted before n-1 traversals are over.

Answer:

An algorithm is said to be incremental if it does not need to recompute everything after a small change. For example: adding an element to a sorted list and sorting it again. If it only takes a few iterations, it would be called incremental.

Bubble sort is incremental when the element is added to the front of the list because it will reach its correct position in the list in the first iteration. But if you add it to the end of the list, the number of iterations required would depend on the position of the element. (Include an example)

Adding onto this ^^:

This is because of the invariant that mentions that in each traversal, the largest unsorted element will get to its final position.

Eg:

Original sorted list: [3, 6, 10, 14, 18, 20]

After appending 13 at the end: [3, 6, 10, 14, 18, 20, 13]

Note that 14, 18 and 20 are not in their final positions and require 3 traversals of the list in order to sort the list.

However, if we append to the front: [13, 3, 6, 10, 14, 18, 20], only one traversal of the list is required (refer back to the invariant)

Answer:

A sorting algorithm is said to be stable if the relative order is maintained after the list has been sorted. For example: [1,,,2]->[1,2,,] this is stable.

Bubble sort is stable because of the strict < comparison in the code (elements are only swapped if they are less than the other element, so equal elements are not swapped and the relative order is maintained). Using <= would make it unstable.

Answer: Selection Sort finds the minimum value for each index of the array and successively does this until the end of the array is reached.

To add on:

Once it “selects” the minimum value in the unsorted portion of the list it then swaps it into the end of the sorted portion of the list, which will be its final position.

Answer: For each iteration of Selection Sort we find the minimum value starting at the 0th index and traverse the list. We store the minimum value in a variable and note the index it was found. We then place the current value of the array at the current index in a temp variable. We replace the current value with the minimum and the value at which minimum value was found with the temp variables value.

Answer: O(n^2) for both, where n is the length of the list

Answer:

Regardless of whether or not a list is sorted, the amount of times we iterate through the list is the same as the selection sort algorithm does not know if all the elements have been sorted without checking. It will still go through itself to find the smallest element and swap it with itself. The algorithm hence takes O(N^2) comparisons, so it has an O(N) complexity.
Feedback: Last sentence O(N^2) not O(N)?

Answer:

[-5, 20, 5, 10, 3]

Answer:

[1, 5, 4, 3, 2, 6]

Answer:

A sorting algorithm is considered stable if it preserves the relative order of items with equal values. This means that if two elements in the list are equal, their order relative to each other remains the same after sorting.

For. e.g. in a list of tuples [(Earl,80), (David,90), (Charlie,70), (Sebastian, 80)] is going to be sorted by the grades of students. Two people in the grades have the same grade 80 - Sebastian and Earl. Earl is at index 0 while Sebastian is at index 3 in the unsorted list - Earl has a lower Index than Sebastian. If the list is sorted by a stable sorting algorithm, to maintain the relative order of all items, Earl would have a lower index than Sebastian in the sorted list. The expected sorted list under a stable sorting algorithm would be:

[(David,90), (Earl,80), (Sebastian,80), (Charlie,70)]

However, in selection sort, as non-adjacent elements are swapped, the relative order of all items in the output may be disrupted. As such, the expected output from the selection sort algorithm would be: v

[(David,90), (Sebastian,80), (Earl,80), (Charlie,70)]

As the relative order under the selection sort algorithm is not preserved, it is not a stable sorting algorithm.

Answer:incremental

An algorithm is said to be incremental if it does not need to recompute everything after a small change/if the algorithm can return a sorted list with the new element within one or few iterations.

Selection sort is not incremental. The algorithm is written in such a way that it will always repeatedly select the smallest element from the unsorted portion of the list and swap it with the first unsorted element. Regardless of whether the new element is placed in the front or back, in each (outer) iteration, selection sort will examine all the remaining unsorted elements to find the minimum (will always perform full scans of the unsorted portion). Hence, to return a sorted list with the new element, it will require (a lot) more than one or few iterations of the algorithm

Answer:

Consider the first element as “sorted” (might not necessarily be true)

Create temp variable for first unsorted number

Check over each number in the sorted partition (decrementing right to left)

If the decremented element is greater than temp, shift it to the right by 1 spot.

Once the decremented element is less than or equal to temp, overwrite the number after the decremented element with temp, thus “inserting” it.

Answer:

Each iteration will increase the number of elements in the sorted partition by 1

Answer:

Best case O(n)

Worst case O(n²)

Answer:

Best: O(n) where n is the number of elements in the array occurs if the array is already sorted. The algorithm will store temp, then compare with the element to the left of it in the sorted partition. Since temp is greater than the element in the sorted partition, it will essentially do nothing because it’s already in correct order. It will repeat this for n elements in the array.

Worst: O(n²) where n is the number of elements in the array. Worst case occurs if the array is sorted in reverse order. For every unsorted element, the algorithm will then have to traverse the entire sorted partition from right to left until it finds the correct position for temp (which is at the beginning). If the program has to traverse the entire sorted partition (O(n)) for n elements, we get O(n²)

Answer:

[-5,5,20,10,3] [incorrect]

Alternative answer (pls check):

[5, 20, -5, 10, 3] because in the first iteration, it compares 5 and 20, and since 20 is greater than 5 it stays in the same position.

Yeye this is correct. The one up there is wrong, and no swaps should be performed!

Answer:

[-7,-1,-4,4,5,6] -> List remains unchanged as -7 at index 0 is smaller than index 1.

Answer:
I’ll assume that there’s a typo in the question given to us and it should’ve said “What does it mean for a sorting algorithm to be incremental”

• A sorting algorithm is stable when it preserves the relative order of the elements with equal values when the unsorted list is sorted

• Insertion sort is always stable as when inserting an element into the sorted portion of the list (S) , it only moves past elements that strictly greater than the element to insert

• If it meets an element with the same value, it does not move past it and stops, thus maintaining the relative order of the elements with equal value.

Answer:

For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same, i.e. when 2 or more items have the same value in an unsorted list, the one which had a lower index in the unsorted list is first.

During the insertion process, when an element (pivot) is being compared to the sorted elements of the list, it will only move past elements which are greater than it, not elements which are less than or equal to it. Hence, insertion sort is stable because when 2 or more items have the same value, the relative order of items remains unchanged.

Answer:

In general for an algorithm, it is expected that it will do a finite set of instructions.

(Feedback: Answer correct but incomplete)

Alternative Answer #1:

An algorithm should have:

• Finite set of well specified but subjective instructions

• It solves the problem

• Input to output relationship

• Halt for problem instance

It can happen that two algorithms solving the same problem can produce non equivalent outputs, because an algorithm can be non deterministic which would produce a different output even if the input is the same each time we run an algorithm usually because the algorithm is probabilistic or contains randomness, An example would be probabilistic algorithms whose behaviours depend on random number generators.

Credit to the Malaysian PASS leader for this answer

Answer:

No, an algorithm has to halt for any problem instance according to the definition in class, therefore the algorithm would have already been designed in a way that it will always halt for any problem instance.

Alternative answer:

No, Algorithm has to halt for any problem instance because algorithms are considered correct if they produce the correct output for every valid input. Therefore algorithms should stop for every problem instances.

Answer:

If the algorithm’s input is an integer, it means it is the number of bits or digits needed to represent the integer where for an integer in general the size is equal to log₂n where n is the input size.

If the algorithm’s input is the collection of elements, the input size is the number of elements in the collection.

If the algorithm’s input is a graph/tree, the input size can be measured in multiple ways, for example, the number of vertices, edges or both.

When we calculate the time complexity of an algorithm we want to know how much time does an algorithm take solving the problem, so we usually measure the number of elementary operations performed in the algorithm.

Answer:

Algorithmic time complexity should be measured with respect to the input size of the algorithm. An example of an input size would be the number of elements in a collection.

When f(n) = O(g(n)) it means mathematically that f(n) is less than some constant multiple of g(n), for all sufficiently large values of n. g(n) is an asymptotic upper bound for f(n) meaning when n becomes very big and it is approaching infinity g(n) provides the tightest upper bound for the runtime of our algorithm.

Answer:

1. f(n) grows faster after a certain value of n, as the gradient of the function f(n) is higher than the gradient of g(N) after a particular input n.

2. The function g(n) grows faster as its rate of change is higher than f(n).

3. The function f(n) has a higher rate of change than the function g(n) so it will grow faster.

Answer:

1.No, f(n) simplifies to O(n^2) given that the dominating component of the function f(n) is 1000^2. (feedback: dominating component should be 1000n^2?) (feedback: not sure if this is right but should you say the dominating component is n^2 because the constant is irrelevant in an asymptotic context?)

As, n^2 not equals g(n) = n log n, the statement that f(n) = O(g(n)) is not true.

2.No as they simplify to f(n) = O(3^n) and g(n) = O(2^n), this means that 3^n grows faster than 2^n thus they are not equivalent.

Answer: Its complexity is O(n), as the number of traversals of the function is related to the total amount of elements by a factor of n

Feedback (Correct): Alternate Answer more i n depth below:

• Let the total number of operations performed on each iteration be the constant k

• Since the function iterates n times, the total number of operations that will occur is n⋅k

• In Big-O notation, this will lend us O(n⋅k), where n is the number of elements in the collection

• Since k is a constant and constant factors are dropped out because they do not reflect asymptotic growth, this will give a time complexity of O(n), where n is the number of elements in the collection

Answer:O(50*n) which can be simplified to O(n) where n is the size of the collection.

This is because our algorithm will perform a constant number of elementary operations 50 times on each element in the collection. As these operations are elementary they have constant time so our complexity would be O(1*50*n) which we saw can be simplified to O(n)

Feedback (Correct): Alternate Answer more in depth below:

• Let the total number of operations performed in each iteration be the constant k

• Since the function iterates 50 times, the total number of operations performed is 50k

• Since 50 and k is a constant which does not depend upon the input size n which is what we're analysing with respect to in Big O, it gives us a time complexity of O(1)

Answer:

• Let the total number of operations performed in each iteration be the constant k

• Since the function iterates n^2 times, the total number of operations performed is k⋅n^2

• This will yield us a time complexity of O(k⋅n^2), where n is the number of elements in the collection

• Since k is a constant, and constants factors are dropped out since they do not reflect asymptotic growth, this will give us a time complexity of O(n^2), where n is the number of elements in the collection

Answer:

• Let the total number of operations performed on each iteration be the constant k

• Since the function iterates n times, the total number of operations that will occur is n⋅k

• In Big-O notation, this will lend us O(n⋅k), where n is the value of the number given

• Since k is a constant and constant factors are dropped out because they do not reflect asymptotic growth, this will give a time complexity of O(n), where n is the number given

Answer:

• Let the total number of operations performed on each iteration be the constant k

• Since the function iterates n^2 times, the total number of operation

• s that will occur is k⋅n^2

• In Big-O notation, this will lend us O(k⋅n^2), where n is the value of the number given

• Since k is a constant and constant factors are dropped out because they do not reflect asymptotic growth, this will give a time complexity of O(n^2), where n is the number given

Answer:

Constant-time complexity is simply donated as O(1).

Answer:

f1(n) + f2(n) will be O(max(f1(n),f2(n)) where n is ____ (not given)

The time complexity of f1(n) + f2(n) will be whichever has a faster growing Big O time.

In this case, f1(n) + f2(n) will be f`1(n) = O(n²) because n² is larger than n*log(n).

This can be seen:

n² = n*n > n*log(n)

since n > log(n)

Answer:

Since they are multiplying each other, we multiply the big O complexities.

f1(n)*f2(n) will be O(n³*log(n)) where n is …. (not given to us)

Answer:

Time complexity refers to the amount of times an algorithm will traverse through the algorithm relative to an input of a specific size. The worst-case complexity is measured when we are given when an input of specific size for which the traversals are maximum, the best-case complexity is when we are given an input of a specific size for which the traversals are minimal.

(Alternate: Worst-case complexity describes the maximum amount of time or resources an algorithm will require for any input of a given size, it is the most time-consuming scenario. It also describes the asymptotic upper bound on the algorithms performance. In contrast, best-case complexity describes the minimum amount of time or resources an algorithm will require for any input of a given size, it is the least time-consuming scenario. It also describes the asymptotic lower bound on the algorithms performance.)

Answer:

func1: O(log(n)) where n is the value of the integer n

func2: O(max(log(a,b)) where a, b are their integer values

func3: O(n²) where n is the number of elements in the list: l

Answer:

The best case complexity of a given function is found when an input is picked such that it may have a lowered amount of operations. (Feedback: Please give according to the examples listed in 20.)

Answer:

An Abstract Data Type (ADT) defines the possible values of the type and their meaning, the operations that can be done on them, but not its implementation, i.e. how the values are stored, how the operations are implemented. Users interact with the data only through the provided operations. Eg. Stack ADT, Queue ADT, List ADT.

Data Types are like ADTs except they have implementation and information on how they’re stored. The possible values for that type, the meaning of those values, the operations that can be done on them, and how those values are implemented are all provided. Eg. int, str etc.

Answer:

The idea behind an abstract data structure is to display the information regarding possible values of a particular type and the operations which can be done on them, without showing the code for them. This is done for the sake of simplification and maintenance - the algorithm for a particular data structure may change, yet it may not impact the usability for one’s code.

Answer:

The capacity is the maximum amount of elements that can be in a data structure, while the length states the amount of elements that actually are in a data structure.

Answer:

• Main property of a Stack ADT

  • An ADT that stores items

  • Its operations follows a Last In First Out (LIFO) process

    • The last element to be added is the first to be deleted

  • Access to any other element is unnecessary (and not allowed)

    • If another element is needed to be accessed, choose a different ADT

Key operations of Stacks are the constructor, push() and pop()

Other common operations include: peek(), is_empty(), is_full(), clear()

• Undo function

• Creating a calculator that evaluates mathematical expressions written in reverse polish notation

• Tracing call frames in recursive functions and examining a program in the runtime stack

Answer:

Best and worst cases for both are O(1). Does anyone know to explain the reasoning behind this other than saying that the operations in the methods are all constant, or is that enough explanation?

Alternative Answer #1 (Revised post feedback below):
Let n = length of the stack. We can just say that as the amount of operations required for items to be pushed remains constant given the capacity of the stack has not been reached, so the best-case is O(1) for push(). In the worst-case scenario for push(), the Stack ADT will be resized if the length of the stack is the same as the size of the stack, making the complexity O(n) in the worst-case scenario for push().

Given that the amount of operations for the items to be popped remain constant throughout all valid scenarios, both the best-case and the worst-case for pop() is O(1).

Push(): O(1) best case, O(n) worst case

Pop(): O(1) best case, O(1) worst case

Feedback to Alt Ans #1:

It is possible for push to be O(n), where n is the capacity of the array, due to resizing?

Feedback to Feedback #1:

I think it depends on how push() is implemented I think…

Answer:

A set is unordered and does not allow for duplicates.

Key operations are the constructor, add(), remove(), member(), union(), difference(), intersection()

Answer:

A bit-vector refers to how the bits 1 and 0 respectively can be used to represent whether or not certain elements are within a particular set. If Item i belongs to the set if the vector has value 1 in the position i - 1, Otherwise, the item is not in the set!

For example:

The set represented by the bit-vectors above has elements {A,B,E,F}. We handle bit vector-based sets by doing bitwise operations. Bit-vectors can only be utilised to represent numbers

Advantages:

Array

• Can store items of any type

• Can support arbitrary sets of arbitrary sizes

• Getting set size is cheap (O(1)) due to the presence of the size variable

Bitvector

• All operations except for size are cheap

Disadvantages:

Array

• All operations except for size are expensive

Bitvector

• Can only store integers

• Number of items is limited by the number of bits in bitvectors (which is architecture dependent)

• Getting set size is expensive

Answer:

• add(self, item):

  • Best: O(1) if the first element in the set is a duplicate, it will terminate early

  • Worst: O(n) where n is the number of elements in the set because we must check every element to see if what we’re about to add is already in the set

• remove(self, item):

  • Best: O(1) if the first element is the one to be removed

  • Worst: O(n) where is the number of elements in the set which occurs if item ends up being the last element in the list

• __len__():

  • Best = Worst = O(1) just return self.length

• union():

  • Best = Worst = O(n*m*c₌₌) where n is the number of elements in set1, m is the number of elements in set2, and c is the cost of comparison. This is the case because for each element in set1 (n elements), check if it’s in set2 (O(m*c₌₌)) to make sure it isn’t already in the set.

• intersection():

  • Best = Worst = O(n*m*c₌₌) where n is the number of elements in set1 and m is the number of elements in set2, with c being the cost of comparison. We must iterate over every element in n (O(n)), then check if it’s in m (O(m*c₌₌)), hence giving us O(n*m*c₌₌)

Answer:
*Please add if you can explain/ justify this more. Not sure if this is enough explanation

• add(self,item):

  • Best = Worst = O(1) because bitwise operations are constant time

• remove(self, item):

  • Best = Worst = O(1) because bitwise operations take constant time

• __len__():

  • Best = Worst = O(number of bits/ bit length)

• union():

  • Best = Worst = O(1). Bitwise operations constant time

• intersection():

  • Best = Worst =O(1) bitwise operations constant time

Answer:

Yes! Python has integers, booleans, floats, strings as primitive data types. They are primitive in the sense that they are the building blocks which all other data types are constructed from. (from PASS slides)

Answer:

• Main property (I think this is asking how they operate?):

  • First in first out, meaning items are added to the end of the queue and removed from the front of the queue.

• Key operations:

  • append(): Adds an item to the end of the queue

  • serve(): Deletes and returns the front of the queue

  • is_empty(): checks if the queue is empty

  • is_full(): checks if the queue is full

  • peek(): returns the first item in the queue without deleting it

• Applications:

  • A queue of customers to show the order in which they should be served.

  • Messaging, in which messages should be viewed in the same order as they are sent.

  • Printer queue

11

Alternative Answer:

(Feedback: Above answer is correct, but some more details)

• Main property: We only have (visible) access to the first element of the queue. We also keep a record of the ‘front’ and ‘back’ address of the queue.

Answer:

• Circular queues

1. Have their front and end connecting to the beginning of the array that they are implemented with. The queue can therefore reuse any space that is freed up when serve() is used.

2. Therefore, another difference is that circular queues are only full when every possible space is filled with an element, as new values can be added to the front indexes of the array due to the queue’s circular nature. This is far more storage efficient than if the queue was linear.

• Linear queues

1. The beginning and rear of the array are separated, meaning even if the queue has items removed from its front this space cannot be reused and must remain empty instead of being filled with append() values.

2. Therefore another difference is that the linear queue is full when a value is added to the last position in it, even if there are empty spaces at the front of the queue as this space can never be reused. This makes them very storage inefficient.

• Which one is better?:

  • Circular queues are better because they can utilise emptied space made by removing elements which is far less wasteful.

Alternative Answer:

(Feedback: Above answer is correct, but some more details)

• Circular queues don’t so much ‘have their front and end connected to the beginning of the array’, rather when the end of the array is indexed in a Circular Queue, the index count will ‘wrap around’ to the beginning of the que. Both Linear and Circular queues have ‘moveable’ ends. But, the Linear Queue will return ‘Is Full’ when the ‘end’ index returns the last index of the array irrespective of whether previous items in the queue have been served prior. In contrast, due to the ‘wrapping around’ of a Circular Queue, the Circular Queue will return ‘Is Full’ only when there are no more available slots in the array.

Answer:

1. append(): Both best and worst case are O(1)

• This is because regardless of the queue length, the process adds to the position indicated by the rear of the queue.

1. serve(): Both best and worst case are O(1)

• This is because regardless of queue length, the process removes the value indicated by the front of the queue.

1. is_full(): Both best and worst case are O(1)

• This process compares the front and the rear of the queue, which follows constant time as these are both accessible constantly.

Alternative Answer append() & serve():

(Feedback: Above answer is correct, but some more details)

• These are all constant time precisely because we keep a record of the memory location of front and end. This is important, because without this record (particularly in a circular queue) we could not identify the appropriate index to serve or append to.

Alternative Answer is_full()

(Feedback: Above answer is slightly incorrect, I think).

• is_full() doesn’t compare equality between the front and back, as this is the normal state on an empty Circular Queue. Instead, it compares length(self) with length(self.array). (Ie, compares the size of all currently used elements with the predefined size of our array). Please see Week 3, Queue ADT, Slide 36.

Answer:

• Main property of a List ADT

  • An ADT used to store items

  • Elements have an order (not necessarily sorted though)

  • Must have direct access to the head (first element)

  • From one position, you can always access the "next" (if any)

• Key operations of the List ADT

  • The key operations for the List ADT are not very well defined and different texts/languages provide very different set of operations

  • However, they do often agree on a core set of operations which includes:

    • Creating, accessing and computing the length

    • Testing whether the list is empty

    • Adding, deleting, finding, retrieving and modifying an element

• Name a few applications where Lists are of use.

  • Contacts of people

  • To-do lists and task management

  • Managing a playlist

Answer:

1. insert():

   1. Best: O(1) which occurs if we basically add the new item to the end of the list. This is because no shuffling is required.

   2. Worst: O(n) where n is the number of elements in the list. The worst case occurs if we add the item to the very beginning of the list, meaning every element in the current list must be shuffled/ shifted to the right which is n operations. Alternatively, this worst case can occur if the list is already full and must be resized.

2. index(): Assuming linear search because binary search would only work on sorted lists.

   1. Best: O(1) if the very first element is the one we’re looking for.

   2. Worst: O(n) where n is the number of elements in the list. This occurs if the element we’re looking for is at the very end of the list.

3. delete_at_index():

   1. Best: O(1) when we delete the last element of the list because there is no need for shuffling

   2. Worst: O(n) where n is the number of elements in the list because we must now shuffle every other element to the left.

Answer:

The main property of a sorted list is that whenever items are added in and removed to the list, they will be sorted in ascending order. The key operations of the sorted list ADT are:

• add(item)

• delete_at_index(index)

• __index_to_add__

• __shuffle_left__

• __shuffle_right__

Sorted lists would be preferred to normal lists when one needs to find a large amount of data from a particular data set - if the list is sorted, binary search instead of linear search to find elements, reducing the complexity of the index(item) method to O(logn).

Answer:

add() - Best case would be O(log(n)), where n is the length of the list. Occurs when an item is added to the end of the list. Worst case, on the other hand, would be O(n), where n is the length of the list. This occurs either when we have to resize the list when it is full OR when we add to the first element, as every item needs to be shuffled right by one.

index()

• Best case: O(1) - When the item we are searching is at the start of the list

• Worst case:

• Linear search: O(n) - Where the n is the length of the list. If the item being searched is at the end of the list, loop will iterate n times.

• Binary search: O(log n) - Where the n is the length of the list. The maximum number of the times we halve the search interval is log₂n, thus yielding the time complexity of O(log n).

Feedback: (added case for Binary Search)

For Best Case for index():

Best case:
When the item we are searching is at the start of the list

Linear Search: O(1), when the item is in the beginning of the list, as it checks the start first

Binary Search: O(1), when the item is in the middle of the list, as it checks the middle first.

Answer: The best case of both searches is O(1), as we can get the desired result 1st try. This occurs when the item is in the middle of the list for binary search, and the start for linear search.

However, as binary search reduces the search size for the sorted list by a half each iteration - we know that the worst-case time complexity is thus O(log(n)), where n is the size of the list. This occurs when the item is either at the start or the end of the list. The worst case for linear search on the other hand would be O(n), where n is the length of the list. This is because we need to iterate through every element to find the last item.

Answer:

Advantages:

• Fast insertion and deletion - no shuffling required to maintain order

• Efficient resizing - Unlike arrays that need complicated process (creating new array, duplicating all elements), it can be easily resized by create/removing nodes

• Less memory use - If there are less than N/2 elements, where N is the capacity of the ADT.

Disadvantages:

• More memory use - If there are more than N/2 elements, where N is the capacity of the ADT.

• Longer time takes to access items - Worst time complexity of O(n), where n is the index, as traversing through the nodes are required. In contrast, arrays have O(1) time complexity as elements can be directly accessed by index.

ADDITION TO ANS ABOVE:

Another Disadvantage is:

• As linked nodes use pointers to access successive nodes it can increase the complexity of the data structure, which may make the linked lists more difficult to maintain.

• Cannot use binary search to find items, we can only use linear search.

Feedback:
Added the definition of n in “Longer time takes to access items” that is, “where n is the index”

Answer:

Assuming that the linked list is a singly linked list:

Feedback (Incorrect): I’m pretty sure Best Case reasoning for insert(index, item) is incorrect, and Worst Case is wrong (should be O(n), where n is the index), and also Best Case reasoning and Worst Case in general is incorrect for delete_at_index() see slides for Linked List ADT page 66.

I also provided an alternate answer considering the cost of comparison just in case the question asks for it.

And also, for the alternate answer for insert(index, item) and delete_an_index, can anyone explain why the lecture slides says that the worst case for insert is O(index), not O(len(self))?

Alternate Answer:

insert(index, item)

Best Case O(1) - occurs if we insert the item at the beginning, then we only need to update the head element and add the previous head as the link to the current head.

Worst case O(index) - this is because everything is constant except for __get_node_at_index (which is O(index)), as we need to traverse through the nodes to find the previous node

index()

Everything is constant except for the cost of comparison and the loop runs until the item is found

Best Case: O(comp) - if the item is at the front of the list as the loop only has to run once

Worst Case: O(comp * len(self)) - if the element is at the rear of the list as the loop have to iterate len(self) times until we reach the end of the list

delete_at_index()

Everything is constant except for __get_node_at_index, which the worst case is O(n), where n is the length of the list.

Best Case: O(1) - occurs if we delete the item at the beginning, then we only need to update self.head to the next head in the list and traversing through the entire nodes is not required

Worst Case: O(n), where n is the length of the list - occurs when the item to delete is at the very end, meaning that we have to traverse the nodes n times, and then updating the previous node’s link.

__get_node_at_index(index)

The loops always executes index times, and all other operations are constant
Best Case = Worst Case: O(index)