CODEWITHSUNDEEP
algorithmgraph-algorithm
Pinsickle
Pinsickle

Reputation: 633

Analysis of Algorithms Notation Confirmation

I'll go ahead and mention that this is homework, but I'm not seeking typical homework help. I'm just wanting confirmation on wording of the question. The question states that my algorithm should be linear in the number of vertices in the graph. I've never seen that wording, is that just saying my running time should be O(|V|)? If so I think I have my solution.

Upvotes: 1

Views: 54

Answers (1)

Hunter McMillen
Hunter McMillen

Reputation: 61540

In analysis of algorithms, algorithms are categorized by efficiency as a function of their input size.

O(|V|) means that your algorithm must examine, or 'touch', every vertex in your graph. So yes, linear in the number of vertices means O(|V|).

For reference, in Big O, Ɵ, or Ω; the two vertical bars mean number of. They are also used to denote length of in some proofs.

Upvotes: 3

Related Questions