# Question 11

**Explain the BigOh notation.**

Â

Time complexity

The Big Oh for the function f(n) states that

`f(n)=O(g(n));Â iffÂ thereÂ existÂ positiveÂ constantsÂ cÂ andÂ dÂ suchÂ that:Â f(n)Â <=c*g(n)Â forÂ allÂ n,n>=d.`

Here are some examples...

`1Â Â Â Â Â Â Â ->Constant`

lognÂ Â Â Â ->Logarithmic

nÂ Â Â Â Â Â Â ->Linear

nlognÂ Â Â ->nlogn

n*nÂ Â Â Â Â ->quadratic

n*n*nÂ Â Â ->cubic

2^nÂ Â Â Â Â ->exponential

n!Â Â Â Â Â Â ->Factorial

We also have a few other notations...

Omega notation

`f(n)=Omega(g(n)),Â iffÂ positiveÂ constantsÂ cÂ andÂ dÂ existÂ suchÂ asÂ f(n)>=cg(n)Â forÂ allÂ n,Â n>=d.`

Theta notation

`f(n)=Theta(g(n)),Â iffÂ positiveÂ constantsÂ c1Â andÂ c2Â andÂ anÂ dÂ existsÂ suchÂ thatÂ c1g(n)<=f(n)<=c2g(n)Â forÂ allÂ n,Â n>=d.`

Little Oh(o)

`f(n)=og(n),Â iffÂ f(n)=Og(n)Â andÂ f(n)!=Omega(g(n)).`

Then there is also something called Space complexity...

Fixed part : This is the independent of the instance characteristics. This typically includes the instruction space (i.e. space for the code), space for simple variables and fixed-size component variables, space for constants, and so on.

Variable part: A variable part that consists of the space needed by the component variables whose size depends on the particular problem instance being solved, dynamically allocated space (to the extent that this space depends on the instance characteristics); and the recursion stack space (in so far as this space depends on the instance characteristics).

A complete description of these concepts is out of the scope of this website. There are plenty of books and millions of pages on the Internet. Help yourself!

# Question 12

**Give the most important types of algorithms.**

Â

There are five important basic designs for algorithms.

They are:

Â

- Divide and conquer : For a function to compute on n inputs the divide and conquer strategy suggests the inputs into a k distinct subsets, 1
- The greedy method : The greedy method suggests that one can devise an algorithm that works in stages, considering one input at a time. At each stage, a decision is made regarding whether a particular input is an optimal solution. An example for solution using greedy method is "knapsack problem". Greedy algorithms attempt not only to find a solution, but to find the ideal solution to any given problem.
- Dynamic programming : Dynamic Programming is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions. An example for algorithm using dynamic programming is "multistage graphs". This class remembers older results and attempts to use this to speed the process of finding new results.
- Back-tracking : Here if we reach a dead-end, we use the stack to pop-off the dead end and try something else we had not tried before. The famous 8-queens problem uses back tracking. Backtracking algorithms test for a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.
- Branch and bound : Branch and bound algorithms form a tree of subproblems to the primary problem, following each branch until it is either solved or lumped in with another branch.

# Question 13

**What is marshalling and demarshalling?**

Â

When objects in memory are to be passed across a network to another host or persisted to storage, their in-memory representation must be converted to a suitable out-of-memory format. This process is called marshalling, and converting back to an in memory representation is called demarshalling. During marshalling, the objects must be respresented with enough information that the destination host can understand the type of object being created. The objects? state data must be converted to the appropriate format. Complex object trees that refer to each other via object references (or pointers) need to refer to each other via some form of ID that is independent of any memory model. During demarshalling, the destination host must reverse all that and must also validate that the objects it receives are consistent with the expected object type (i.e. it validate that it doesn?t get a string where it expects a number).