To hack java HackerRank questions-For beginners
What is an algorithm?
Basically, an algorithm is a step by step procedure to solve any problem.
Analyze algorithms
To analyze the algorithm, we always use high number of input values. Because in real time applications, the input value is always high.
The order of growth of an algorithm (time complexity of an algorithm)
The order of growth means the changing behavior (execution time) of an algorithm when the input size increases. The algorithm may use to sort, search values etc.
For searching algorithm, we may locate the required element in the first position of an element set, in a middle position or in the last position. When the size of the input values are increasing, it affects the worst (the last position) and average cases (, in a middle position).
Because locating an element in an average position should be searched at least a half of a list. Therefore, when we write a searching algorithm, these three cases should be considered.
That is why, we use searching techniques instead of searching the elements by comparing values one by one.
· When analyze an algorithm, we first figure out the operation of the algorithm. That means that the algorithm is used to either search or sort etc.
· As an example, if it is a searching algorithm, there are three cases such as element in the first position, element is the last position or element in the middle position.
· So, when the input size increases, we need to analyze how these three cases behave based on our algorithm.
Technically, order of growth (time complexity) means a function that represents the execution time as the input size increases.
The order of growth function can be represented as
· Big O
· Big Ω
· Big θ
Big O (worst case) — upper bound
We will take a function which was written to solve a problem.
The running time of the function as the input size increases is denoted as f (n) If all other rest of the solutions are lower than f (n) , the f (n) is the worst case and it denotes as O (f(n)).
Furthermore, f (n) may be a linear function, quadric function or constant
For instance, O (n) — linear — The execution time varies as the inputs size increases in a linear way
When we analyze a newly develop algorithm, the users always need to know about the upper bound algorithm. Because Big Theta and Big Omega are always below the Big O in terms of the execution time.
Brute force algorithm
A brute force algorithm blindly iterates an entire domain of possible solutions in search of one or more solutions which satisfy a condition.
Finding the order of the growth of an algorithm
[1]
Here, this statements is printed 100 times.
Then, f (n) = n, O (n), f (n) is a linear function
[2]
Here, this statements is printed 50 times.
Then, f (n) = n/2, O (n), f (n) is a linear function
[3]
Here, first statements is printed 100 times and second statement is printed 99 times
Then, f (n) = n², O (n²), f (n) is a quadric function
[4]
i->1, 2, 4, 8………2^p
Then p = log 2^n (here, n=100), therefore O (log 2^n )
