Top Algorithms Interview Questions

>A function t[n] is said to be in θ [g[n]], denoted by t[n] ε θ [g[n]], if t[n] is bounded both above & below by some constant multiple of g[n] for all large n.
>Theta can be used to denote tight bounds of an algorithm.
>f(n) is θ(g(n)) if and only if f(n) is O(g(n)) and f(n) is Ω(g(n)).

1. The running time of each assignment read and write statement can usually be taken to be O(1).

2. The running time of a sequence of statements is determined by the sum rule.
I.e. the running time of the sequence is, to with in a constant factor, the largest running time of any statement in the sequence.

3. The running time of an if–statement is the cost of conditionally executed statements, plus the time for evaluating the condition. The time to evaluate the condition is normally O(1) the time for an if–then–else construct is the time to evaluate the condition plus the larger of the time needed for the statements executed when the condition is true and the time for the statements executed when the condition is false.

4. The time to execute a loop is the sum, over all times around the loop, the time to execute the body and the time to evaluate the condition for termination (usually the latter is O(1)). Often this time is, neglected constant factors, the product of the number of times around the loop and the largest possible time for one execution of the body, but we must consider each loop separately to make sure.

EXAMPLE:

statement;
>>here we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not change in relation to N.

for(i=0; i < N; i++)
{
statement;
}
>>The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

for(i=0; i < N; i++)
{
for(j=0; j < N;j++)
{
statement;
}
}
>>This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N

ALGORITHM: Euclid_gcd[m, n]
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n
m←n
n←r
return m

The notations describe different rate-of-growth relations between the defining function and the defined set of function. They are used to compare two function sizes.
It is a mathematical tool to represent the complexities and allow us to analyze running time of an algorithm by identifying its behavior as the input size for the algorithm increases.
The three commonly used notations are:
> Big Oh notation
> Big Omega notation
> Big Theata notation