Question

**How to measure the time complexity of an
algorithm?**

- Identify an important operation in the algorithm that is executed most frequently.
- Express the number of times it is executed as a function of N.
- Convert this expression into the Big-O notation.

**A. For each of the three fragments of code, what is its
worst-case time complexity, in the form " O(…)". (Use the
given solution to the first problem as a
model) **

**//----------------- This is a sample problem – solved
------**

**Given an array a of size N, what is the
complexity?**

** int i=n, x=0;**

** while (i>0) {**

** i--;**

** x = x +
a[i];**

** }**

What is the most frequent operation performed? ___addition____________________

Expression showing the number of times it is performed____ N _______

Time Complexity in Big-O Notation____ O(N) __________________________

**//1.--------------------------------------------------------------**

**Given three 2-dimensional arrays A, B, C of size N x N,
what is the complexity?**

** for (int i=0; i<N; i++)
{**

** for (int k=0;
k<N; k++) {**

** int
x=0;**

** for
(int j=0; j<N; j++) {**

** x
= x + A[i][j] * B[j][k];**

** }**

** C[i][k]
= x;**

** }**

** }**

What is a (name one) most frequent operation performed? ___________

Expression showing the number of times it is performed ______

Time Complexity in Big-O Notation___ O(_____) ___________________________

**//2.--------------------------------------------------------------**

**Given an array of size N, what is the
complexity?**

** int m = A[0];**

** for (int i=1; i<N;
i++)**

** { if (A[i]
> m) m = A[i]; }**

** int k = 0;**

** for (int i=0; i<N;
i++)**

** { if (A[i] == m)
k++; }**

What is a (name one) most frequent operation performed?______________________

Expression showing the number of times it is performed ___________

Time Complexity in Big-O Notation O( ) _____________________________________________________

**//3.--------------------------------------------------------------**

**int mult(int N, int
M)**

**{**

**
int s = 0;**

**
while (N > 0)**

**
{**

**
s = s + M;**

**
N = N-1;**

**
}**

**
return s;**

**}**

What is a (name one) most frequent operation performed?______________________

Expression showing the number of times it is performed___________

Time Complexity in Big-O Notation O( ) _______________________________________________________

**4**. **The following method computes the
value of x raised to the power of n, where n is a positive integer.
(For example, power(3, 4) would return the value of 3 ^{4},
i.e. 81. What is the time complexity of this method (as a function
of n?)**

**public int power(int m, int
n) //m raised to the power
n**

** **
**{**

**
int res = 1; int p = m;**

** **
**while (n != 0)**

**
{**

**
if (n%2 == 1)**

**
res = res * p;**

**
p = p*p;**

**
n = n/2;**

**
}**

**
return res;**

** }**

What is a (name one) most frequent operation performed? ______________________

Expression showing the number of times it is performed___________

Time Complexity in Big-O Notation O( ) ____________________________________________________

**B. For each of the following problems, think about an
algorithm to solve it. Write a segment of java code showing how you
would solve it (i.e. code your algorithm in Java) analyze the
algorithm and indicate its time complexity. Assume that a and b are
integer arrays of size N.**

**Here is a sample solved problem: An algorithm to decide
if a given number is a prime number:**

**public boolean isPrime(int n)**

**{**

**if (n == 2)**

** return true;
//Done, we already know n is
prime**

**int div = 3;
//start the possible divisors at 3**

**while (div < Math.sqrt(n))**

** {**

**
if ( n % div == 0)
//we found a divisor**

**
return
false; //so n is not prime**

**
div = div + 2;
//if not, try the next
number**

** } **

**return true****;** **//No
divisor was found. So, num is a prime**

**}**

**Analysis of the algorithm (example):**

Typical Operation: % or +

Number of times performed: Goes up to sqrt(n), increments by 2,
therefore in the worst case this is done n^{1/2} / 2
times

Time complexity = n^{1/2}

**a.**
Print the value at the middle of the array (You can assume that the
length of the array is an odd number). (Example: if a = {5, 3, 6,
2, 1} it should print 6.)

Time Complexity of above problem in Big-O Notation O( )

b. Print the
smallest element of the array ** a** (assuming
that a is NOT sorted)

Time Complexity of above problem in Big-O Notation O( )

c. Print the
smallest element of the array *a* (assuming a is sorted in
ascending order)

Time Complexity of above problem in Big-O Notation O( )

d. A "pair" is
two *consecutive* locations in the array having the same
value. (Note: {2, 3, 3, 4, 2} has a pair 3, 3. But, {4, 5, 2, 9, 2}
doesn't have a pair). Find if the array *a* has a pair in
it.

Time Complexity of above problem in Big-O Notation O( )

e. Find if any
two values in the array are the same (i.e. *a* has a
repeated element). For example {2,3,3,4,2} has two repeated
elements but {4,5,2,9,6} doesn't have repeated elements.

Time Complexity of above problem in Big-O Notation O( )

Answer #1

A)

1)

**Addition of x with the product of****A[i][j] and B[j][k].****N****O(N^3)**

**2)**

**Checking the condition whether A[i] > m****N****O(N)**

**3)**

**Addition****N****O(N)**

**4)**

**Division of n by 2.****N****O(logN)**

**B)**

**a) A simple way to solve this is storing the half of
size of array in a variable and printing the element of array at
that particular index.**

**Ex : A={5,3,6,2,1} . Size of array(N)=5;
k=N/2=2.**

**Now, A[2]=6 i.e middle element of array.**

**We get correct answer always because size of array is
odd.**

**int k=N/2,x; //where N is the size of array**

**x=A[k];**

**return x;**

**Analysis:**

**Since there is no loop and the no. of operations do not
depend on value of N time complexity will be O(1)**

**Time complexity : O(1)**

**b)**

**int x=INT_MAX; //initializing x as maximum int
value**

**for(int i=0;i<N;i++)**

**{**

**if(x<A[i]) { x=A[i]; }**

**}**

**return x;**

**Analysis :**

**There is just one simple loop that runs N
times.**

**Time complexity : O(N)**

**c)**

**Since,the array is sorted in ascending order the 1st
element will be the smallest.**

**int k=A[0];**

**return k;**

**Analysis:**

**Since there is no loop and the no. of operations do not
depend on value of N time complexity will be O(1)**

**Time complexity : O(1)**

**d)**

**int flag=0;**

**for(int i=0;i<N-1;i++)**

**{**

**if(A[i]==A[i+1]) flag=1;**

**}**

**if(flag==1)**

**System.out.println("Pair exists" );**

**else**

**System.out.println("Pair doesn't exist");**

**Analysis :**

**There is just one simple loop that runs N
times.**

**Time complexity : O(N)**

**e)**

**int flag=0;**

**for(int i=0;i<N;i++)**

**{**

**for(int j=i+1;j<N;j++)**

**{**

**if(A[i]==A[j]) flag=1;**

**}**

**}**

**if(flag==1)**

**System.out.println("repeated elements**
**exist" );**

**else**

**System.out.println("repeated elements**
**do not exist");**

**Analysis :**

**There are 2 nested loops, each runs N times.So 2 loops
N*N times.**

**Time complexity : O(N^2)**

Use Big-O Notation to characterize the computational cost of
algorithm A1 and A2. The complexity of A1 is 10000 * n, with n
being the number elements processed in A1. The complexity of A2 is
100 * n, with n elements in A2. State in Big-O notation the cost of
f1, with f1(x) = log2(2x) – 14x + 3 sqrt(x) + 12x^2 - 150 this is
also a theoretical question just answer no code.

Given the recursive bubble sort algorithm, analyze its time
complexity in terms of Big O.
bubbleSort(A[], n)
{
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (i=0; i<n-1; i++)
if (A[i] > A[i+1])
swap(A[i], A[i+1]);
// Largest element is fixed,
// recur for remaining array
bubbleSort(A, n-1);
}

Restricted structures such as stack and queue are fast, but they
do not support access in the key field mode.
Group of answer choices
True
False
Big O analysis evaluates an algorithm based on its _________
performance.
Group of answer choices
A. average-case
B. best-case
C. worst-case
Which of the following algorithms is the fastest in speed?
Group of answer choices
A. Polynomial time algorithm
B. Linear time algorithm
C. Exponential time algorithm
The following code gives an implementation of...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

Determine the order of complexity for the following
algorithm:
function(int n) {
int l, u, m;
l=0; u= n-1;
while (l<u) {
m= (l+u)/2;
if (a[m] < x) l= m+1;
else if (a[m] >x) u=m-1;
else return
“found”
}
return (“not found”);
}

Given the following algorithm, matching each statement to the
correct sequence for complexity analysis.
procedure Alg3(A): A is a list of n integers
1 for i = 1 to n-1 do
2 x=aix=ai
3 j = i − 1
4 while (j ≥≥ 0) do
5 if x≥ajx≥aj then
6 break
7 end if
8 aj+1=ajaj+1=aj
9 j = j − 1
a end while
b aj+1=xaj+1=x
c end for
d return A
The complexity of this algorithm is O(n2)O(n2)...

a)
Suppose that a particular algorithm has time complexity T(n) = 3 x
2^n, and that executing an implementation of it on a particular
machine takes t seconds for n inputs. Now suppose that we are
presented with a machine that is 64 times as fast. How many inputs
could we process on the new machine in t seconds?
b) Suppose that another algorithm has time complexity T(n) =
n^2, and that executing an implementation of it on a particular...

Analyze the worst case running time of the following code in
“big-Oh” notation in terms of the variable n.
a. void fdisp1(int n) { for(int i=0; i < n; i++) { for(int
j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m
< n; m++) { System.out.println("Hi I am Here"); } } } } }
b. voidprintAllPossibleOrderedPairs(intarr[], int size) { for
(int i = 0; i < size; i++) { for (int j =...

What is the time complexity of the following code? (in big-O
notaion)
sum = 0
count = 0
var1 = 0
for: i=1 to n{
sum = sum+i
for j=1 to [(3i+2i)(5n)(2i)]{
var1 = sum+count}
}
for m = i to j*j{
sum = sum*sum
var2 = sum - (count+3)}

Find the worst-case complexity of the algorithm below. Show your
work.
UFSizeCalc
Input: uf: Union-Find array
of size n
Input: n: size of uf
Output: size array for uf; that is, an
array s such that s[r] equals the number of
elements in the Union-Find tree rooted at r, for every
root r (s may have any value for indexes that are
not roots of uf)
Pseudocode:
For i = 1 to n
uf.Find(i)
size = Array(n)
Initialize size to be...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 2 minutes ago

asked 53 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago