ITA - Week 2 Flashcards
1
Q
What is Proof of Correctness
A
Whether the algorithm works correctly for any legitimate input
2
Q
What is the Time Complexity Analysis
A
Finds out how fast the algorithm runs
3
Q
What is the Space Complexity Analysis
A
Finds out how much memory the algorithm requires
4
Q
What is Induction
A
A technique to prove that a property holds for all natural numbers (or all members of an infinite sequence)
5
Q
What are the three steps of Induction
A
Base Case -> Induction Step -> Conclusion
6
Q
What happens in the base case
A
N = 1 is tested
7
Q
What happens in the induction step
A
Assume property holds for n=k, then substitute n for k+1
8
Q
What happens in the conclusion
A
A statement is made saying that base case and induction step are true, so proven by induction
