Time complexity Flashcards Preview

DAST > Time complexity > Flashcards

Flashcards in Time complexity Deck (9)
Loading flashcards...
1
Q

Union find data structure includes three operations. What are they? And what are their time complexities using a Linked List?

A

Make_set(x): O(1)
Find(x): O(1)
Union(x,y): O(n). Unless you add the shorter list to the longer one, and then X’s pointer will only get updated O(log(n)) times.

2
Q

How many times can you do Union(x,y) in a data structure that holds n objects?

A

n-1

3
Q

How many times will you need to update X’s pointer if you do n union operations?

A

log(n)
Because you only update X’s pointer if it is in the smaller group. You only need to update the pointer if you are joining a group that’s double X’s size. And you can only double X’s size log(n) times before you reach the size of the group - n.

4
Q

What’s the total time complexity of joining two groups where you do m steps of make_set, union and find?

A

O(m+nlogn)

A total of m make_set and union operations which each take O(1)*m = O(m)

For any given X, its pointer will be updated at most O(logn) times. We have n X’s so in total O(nlogn)

5
Q

כמה צלעות יש בעץ פורש על
N
קודקודים?

A

יש בדיוק
n-1
צלעות

6
Q

Union find data structure includes three operations. What are they? And what are their time complexities using a Forest?

A

Make_set: O(1)
Find: O(n)
Union(x,y) = Union(find(x),find(y)) –> O(n^2) without adding the shorter list to the longer one.

7
Q

What is Kruskal’s algorithm?

A

An algorithm used to find a minimum spanning tree

8
Q

What are the 3 main steps in Kruskal’s algorithm?

A
  1. Initialize the data
    structure (by calling Make_set(v) for every v in V)
  2. Sort all the edges from smallest to largest.
  3. Pick the smallest edge and see if it forms a cycle in the spanning tree so far.
    If yes - discard.
    If no - add it to the tree (union)
    Repeat step 3 until there are (v-1) edges in the tree.
9
Q

What is the time complexity of Kruskal’s algorithm?

A
  1. Initialize the data structure by calling (Make_set(v) n times) –> O(1)*n = O(n).
  2. Sort the edges from smallest to largest –> O(mlogm), where m is the number of edges.
  3. The union and find operations take m+nlogn

Total: O(mlogm + m + nlogn)