Flashcards in CS50 Week 4 Deck (18):
What is the O of merge sort?
What is the \Omega of merge sort?
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
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?
What is the syntax for dereferencing?
What does dereferencing mean?
Go to the address stored in the pointer.
What is the syntax for passing a memory address to a function?
where x is the variable.
What is the string type, as contained in the CS50 library?
How are strings compared to each other?
it is in string.h
It returns 0 if two strings are identical
What function allocates memory, and how does it work?
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))
char* pointer = malloc(6 * sizeof(char))