CS50 Week 4 Flashcards
What is the O of merge sort?
nlog(n)
What is the \Omega of merge sort?
nlog(n)
When the O and \Omega of an algorithm are the same, how is that denoted?
The algorithm’s runtime can be described as Theta(n)
n is the appropriate runtime.
What is the pseudocode implementation of merge sort?
On input of n elements:
If n < 2
Return;
Else:
Sort left half of elements;
Sort right half of elements;
Merge sorted halves;
What is the tradeoff when considering merge sort?
You trade efficiency for speed. Specifically, more memory is required of merge sort, because a second list is needed for intermediate storage.
Why is merge sort Theta nlog(n)?
The log(n) portion is the breakdown of he list into halves.
the n constant reflects merging the lists together.
What is the basic concept of recursion?
Using a function to call itself using modified arguments, until a base case is reached that returns without calling itself.
When a variable is passed to a function, what is really passed?
A copy of that variable.
What is the syntax for a pointer?
type*
What is the syntax for dereferencing?
*type
What does dereferencing mean?
Go to the address stored in the pointer.
What is the syntax for passing a memory address to a function?
&x
where x is the variable.
What is the string type, as contained in the CS50 library?
A char*
How are strings compared to each other?
strcmp()
it is in string.h
It returns 0 if two strings are identical
What function allocates memory, and how does it work?
malloc(n)
malloc will allocate memory of n bytes and return the address of the first byte in memory?
How many bytes are needed to copy a string?
One more than the number of characters in the string. We must allocate space for the \0.
What is a convenient way to store a number of a given data type
type* pointer = malloc(n * sizeof(type))
for example:
char* pointer = malloc(6 * sizeof(char))
What happens to memory created by malloc when the function ends?
Nothing, it stays around in the heap. That’s why it needs to be freed.
