Tutor profile: Robert L.
Subject: Computer Science (General)
I am really confused when it comes to Big O notation. What does it really mean?
The Big O analysis of an algorithm is meant to give the user of the algorithm some idea of how the algorithm will behave as the size of the data set being processed by the algorithm grows. Also, the Big O analysis always assumes the worst case scenario, Lets look at some examples: Example 1: If the Big O of an algorithm is O(N), this means the time to process the data grows linearly. So for example, if it takes 100 seconds to process 1 million data items, then it should take approximately 200 seconds to process 2 million data items. A linear search would be an example of such an algorithm. Example 2: If the Big O of an algorithm is O(1), this means the time to process the data is the same regardless of the size of the data. So for example, if it takes .00000000001 seconds to process 1 million data items, then it should take approximately the same time to process 2 million data items. Returning the first item in a container would be an example of such an algorithm. Example 3: If the Big O of an algorithm is O(NlogN), this means the time to process the data is greater than N but less than N*N. Admittedly, this still allows for a great deal of variance in the performance of the algorithm. So for example, if it takes 10 seconds to process 1 million data items, then it should take more than 20 seconds but less than 40 seconds to process 2 million data items. More efficient sorts like a Quick Sort algorithm have this type of behaviour.
Subject: C++ Programming
When deciding which template container to use in a C++ application, which template container should a programmer generally default to?
C++ provides several different template containers. Some examples are array<type,size> , vector<type>, list<type>, set<type>, deque<type>, etc. The most flexible of these containers that a C++ programmer may choose from that is still reasonably efficient is the vector<type> container. This container can both increase in size and shrink in size when required and supports direct access operations. Therefore vector<type> is the container that should first be considered. The other available containers are generally more specialized with the exception of array<type,size>. For example, list<type> is implemented as a doubly linked list and therefore does not support direct access operations. And though array<type,size> is the most efficient of the template containers, it is static in size and is therefore less flexible than the vector<type> container.
Subject: C Programming
What is the difference betwen the pre and post increment operators?
When used in a stand alone statement, there is no actual difference in the final result. For example: int i = 10; ++i; // pre-increment of i. i will be incremented to value 11 and if instead: int i = 10; i++; // post-increment of i. i will be incremented to value 11 produce the same final result, namely i has the value 11 after the increment. But when used as part of a C language expression, when the pre-increment is used, the variable will first be incremented and then the new value used in the expression. When the post-incrment is used, the variable will also be incremented, but the original value of the variable will be used in the expression. For example: int i = 10; printf("i's value is: %d", ++i); // 11 will be output for i. printf("i's value is: %d", ++i); // 11 will again be output for i but if instead: int i = 10; printf("i's value is: %d", i++); // 10 will be output for i. But i will be incremented! printf("i's value is: %d", ++i); // 11 will now be output for i You should note that the pre-increment is more efficient to implement than the post-increment and therefore most compilers will automatically convert a post-increment operation to a pre-increment operation if there isn't a good reason to do a post increment. For example, in the following statement: for (int i = 0; i < max ; i++) the post-increment in the for statement is a stand alone increment (like the very first examples above) and therefore need not be a post-increment and most, if not all, compilers will optimize the for statement to become after compilation: for (int i = 0; i < max ; ++i)
needs and Robert will reply soon.