ANONYMOUS wrote Yes, you will get full marks if I can understand that you have understood.

ANONYMOUS wrote You should explain exactly how much is required to make it understandable.

ANONYMOUS wrote You should analyse the time complexities of all parts of an algorithm. The analysis of non-dominant parts will cost you (may be) two more sentences and half a minute of writing.

ANONYMOUS wrote K is a variable here, not a constant, so we can't do what you have written. K is a constant only for a specific instance. Suppose you have to find n smallest elements? It will be an O(n) algorithm according to your logic. That will br...

ANONYMOUS wrote Python code of what? There is no question that requires writing code.

ANONYMOUS wrote I only expect you to know the complexity that has been discussed in the lectures.

Thank you, I would love to see meaningful diagrams for explanations.

Merging one single layer is O(n) because each element is processed once. Since this needs to be done log n times, because there are log n 'layers' in the tree created when subdividing the list, the overall complexity of merging is O(n log n). At leas...

Hi, For to explain the time complexity of many algorithms, especially those involving things like binary recursion, would It be acceptable to use diagrams to aid in explanations complexity analysis in the exam. Thank you for your time.

Kruskal's algorithm has complexity of O(ElogV) but in class we learnt an implementation using lists where it comes out to O((E V)logV). What would we be expected to use when discussing complexities in the exam?

Anyone know if it's worth memorizing python codes for data structures since the practice exams asked previous students to write code in Java. I know the lecturer said not to memorize pseudocode, did the same apply to this?

Sorry, when you say it's overall O(N logN) are you referring to a merge sort or a merge within a merge sort? The question I'm trying to figure out is Explain the merge step of the mergesort algorithm. What is the overall complexity of merging in the ...

THANK YOU

Q2a. A heap can be constructed in O(n) time for n inputs. Design an algorithm for finding the k-th smallest element in an unsorted array of length n that is faster than O(n log n) asymptotically. Analyse the complexity of your algorithm assuming k as...

Hi, I was just wondering for exam questions that require us to explain the time complexity, should we explain just how the dominant term is reached or the time complexity for the entire algorithm? For example, if an algorithm takes an overall time of ...

a super simple simplification is that amortized average for the first question of the second test it says A cyclist can travel 24 km hour when wind is blowing from behind, and 12 km hour against the wind. The cyclist travels A to B and then B to A. ...

merge() is O(n) and mergesort() is O(n log(n)). mergesort() repeatedly divides the array into subarrays until each subarray is size 1. This halving takes O(log(n)) steps and forms a complete binary tree with depth log(n). And for each level of divis...

Hi there, I was wondering if merge takes O(n) or O(nlogn) time as I've seen several different answers. Which is correct? Does merge work differently within a merge-sort leading to there being two values for complexity?

This is part of a question given in the practice exams. What type of answer would be expected? (I know we can't be given the answers, I mean the format structure) Are we supposed to be giving a formula; similar to how the lecture 8? How much would we ...

Having some trouble wrapping my head around this concept. Is there an equation that fits all solutions when we are looking for this type of analysis? Or do we have to derive one? Also, regarding Q1 of the second mid sem test, the question about amorti...