[CS50] Week 3 Section

 

 

 

1. Thought Question ( Ω notation )

 

• Suppose that you create a new algorithm and access its runtime.
• The fewest steps this algorithm will ever take is 2, and only 2.
• What is the Ω notation for this algorithm?

→ My answer : Ω(2) 

→ The answer : Ω(1)

     :  Computer scientists like to think of things as being on the order of some number of steps. And whether it takes two, three, four, if it takes some fixed number of steps, we'll say it operates in  Ω(1) to symbolize that it just takes some finite number of steps in the best case.

 

★ We don't care about small numbers! We just care about these common notations:

• O(1) / O(log(N)) / O(N) / O(N^2)
•  Ω(1) /  Ω(log(N)) /  Ω(N) /  Ω(N^2)

 

 

 

 

2.   Factorial

 

: the product of an integer and all the integers below it 

 

ex)

            1! = 1

        2! = 2*1

    3! = 3*2*1

4! = 4*3*2*1 

...

 

→ The concept of recursion 

1! = 1 (base case)

2! = 2*1!

3! = 3*2!

4! = 4*3!

 

int factorial(int n)
{
	//Implement factorial function
    
    //Base case
    if (n == 1)
    {
    	return n;
    }
    
    return n * factorial(n - 1);
}

 

 

Q. Is recursion faster than using regular loop?

A. It certainly is. At the same time, it isn't always necessarily faster. 
     It just means we're trying to solve the problem by first solving a smaller problem in that question.