Assignment: Analyzing Algorithm Time Complexity and Efficiency

This document provides a detailed analysis of algorithm complexity, focusing on time complexity. It explains the basic rules for determining time complexity, including the impact of statements, loops, and nested loops. The solution analyzes a brute force algorithm, calculating its time complexity as O(max-n squared). Additionally, it discusses Kosaraju's algorithm, its time complexity (O(V+E)), and its application in a Java implementation. The assignment references relevant research papers on improving algorithm complexity and explores different scenarios and algorithm types. This assignment is a valuable resource for students studying theoretical computer science and algorithm analysis, providing insights into the efficiency and performance of algorithms.

Running Head: ALGORITHM COMPLEXITY 1
Algorithm Complexity
Institution
Date
Name

ALGORITHM COMPLEXITY
2
The given problem is nothing but to look for the time complexity of the algorithm. We will go
through the basic rules listed below:
1. Every statement or instruction takes 0(1) time in order to execute. For example, it
executes for one time.
2. In a case where we have loops, its time complexity that goes on a loop is the number of
times the instructions get executed within that loop.
Example:
For(int i=0; i<n; i++);
{
Printf(“Hello Buddy”); _____> n times
}
For the above example, Hello buddy is going to be printed for n times
This shows 0(n) time.
3. Whenever we have nested loops then it will be the number of times the outer loop will
run multiplied by the loop inner running. The time complexity of the algorithm in this
case will be the number of times the inner loop is executed.
Example:
For(int i=0; i<n; i++) _____> n times
{
For (int i=0; i<n; i++) _______> n*n times
{
Printf(“Hello Budy”); _______> n*n times
}
}
In this example, Hello Budy will be printed (n*n times). Therefore the time complexity of
thealgorithm will be inner statements executed … as in:
0(n*n) = 0(n squared)
4. When we try finding the time complexity, we should take the order having the bigger
power.
Example:
Int a; +n
For(int i=0; i<n; i++) + n
For(int i=0; i<n; i++)
Printf(“Hello buddy”) +n
Time complexity = 1+n +n squared == 0(n squared) and we take the biggest degree.

ALGORITHM COMPLEXITY
3
Given the problem.
Double brute force(point* pt, int max n, point*n , point* b)
Execute each statement….
{
Int I,j; _________> 0(1)
Double d, max-d=0; _____>0(1)
For(int i=0; i<n; i++) ____>0(max-n)
{ for (int i=0; i<n; i++) _____>(max-n*max-n)
{
d= dist(pt(i), pt(j);
If(d<=max-d) continue; + (max-n* max-n)
a = pt(i);
b = pt(j);
min-d=d;
}
}
Return max-d; ____>0(1)
}
Time complexity = 0(1)+0(1)+0 (max-n) +0(5(max-n squared) + 0(1)
Here, the biggest degree is 2 from squared thus
Time complexity = 0 (max-n squared) after removing the constants
Assumption made: It runs 0(1) TIMES AND IT IS GIVEN THE NAME 0(MAX-N
SQUARED) TIMES
Next Question:
This code implements the Kosaraju’s DFS based simple algorithm in JAVA.
Time Complexity: Time multifaceted nature of this algorithm usage is normal as Depth
First Search which is O(V+E) if the graph is well represented to utilizing nearness list
portrayal.
Scenarios

ALGORITHM COMPLEXITY
4
Algorithm Type Parallel On-the-Fly Complexity Description
Kosaraju’s SCC X X O(V) Basic Two
Pass
Algorithm
References
Lee, P. J., Bui, T. A., & Yao, S. R. (2019, January). IMPROVE THE HEVC
ALGORITHM COMPLEXITY BASED ON THE VISUAL PERCEPTION.
In 2019 IEEE International Conference on Consumer Electronics (ICCE) (pp. 1-
4). IEEE.
Liu, J., Grant, S. L., & Benesty, J. (2015). A low complexity reweighted proportionate
affine projection algorithm with memory and row action projection. EURASIP
Journal on Advances in Signal Processing, 2015(1), 99.