Anki Deck Changes

Commit: 87d73046 - formatting change

Author: obrhubr <obrhubr@gmail.com>

Date: 2026-02-06T18:14:09+01:00

Changes: 1 note(s) changed (0 added, 1 modified, 0 deleted)

Note 1: ETH::1. Semester::A&D

Deck: ETH::1. Semester::A&D
Note Type: Horvath Cloze
GUID: B/7aNL0zYE
modified

Before

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm PlsFix::DUPLICATE
Boruvka's Algorithm has a runtime of  \(O((|V| + |E|) \log |V|)\).

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm PlsFix::DUPLICATE
Boruvka's Algorithm has a runtime of  \(O((|V| + |E|) \log |V|)\).
During each iteration, we examine all edges to find the cheapest one: \(O(|V| + |E|)\):
  1. Run DFS to find the connected components: \(O(|V| + |E|)\)
  2. Find the cheapest one \(O(|E|)\)
We iterate a total of \(\log_2 |V|\) times as each iteration halves the number of connected components.

After

Front

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm PlsFix::DUPLICATE
Boruvka's Algorithm has a runtime of  \(O((|V| + |E|) \log |V|)\).

Back

ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm PlsFix::DUPLICATE
Boruvka's Algorithm has a runtime of  \(O((|V| + |E|) \log |V|)\).
During each iteration, we examine all edges to find the cheapest one: \(O(|V| + |E|)\):
  1. Run DFS to find the connected components (ZHKs): \(O(|V| + |E|)\)
  2. Find the cheapest one \(O(|E|)\)
We iterate a total of \(\log_2 |V|\) times as each iteration halves the number of connected components.
Field-by-field Comparison
Field Before After
Extra During each iteration, we examine all edges to find the cheapest one:&nbsp;\(O(|V| + |E|)\):<br><ol><li>Run DFS to find the connected components:&nbsp;\(O(|V| + |E|)\)</li><li>Find the cheapest one&nbsp;\(O(|E|)\)</li></ol>We iterate a total of&nbsp;\(\log_2 |V|\)&nbsp;times as each iteration halves the number of connected components. During each iteration, we examine all edges to find the cheapest one:&nbsp;\(O(|V| + |E|)\):<br><ol><li>Run DFS to find the connected components (ZHKs): \(O(|V| + |E|)\)</li><li>Find the cheapest one&nbsp;\(O(|E|)\)</li></ol>We iterate a total of&nbsp;\(\log_2 |V|\)&nbsp;times as each iteration halves the number of connected components.
Tags: ETH::1._Semester::A&D::11._Minimum_Spanning_Trees::1._Boruvka's_Algorithm PlsFix::DUPLICATE
↑ Top