Scribd
Upload
34 views3 pages

Algorithm Analysis and Complexity Tasks

The document outlines a series of assignments focused on algorithm analysis, including ordering functions by growth rate and analyzing the running time of various code snippets using Big-Oh notation. It also includes tasks related to recursive functions, evaluating mathematical functions, and determining the primality of integers. Each assignment requires a detailed understanding of algorithm complexity and efficiency.

Uploaded by

Lam Tran Nguyen
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
34 views3 pages

Algorithm Analysis and Complexity Tasks

The document outlines a series of assignments focused on algorithm analysis, including ordering functions by growth rate and analyzing the running time of various code snippets using Big-Oh notation. It also includes tasks related to recursive functions, evaluating mathematical functions, and determining the primality of integers. Each assignment requires a detailed understanding of algorithm complexity and efficiency.

Uploaded by

Lam Tran Nguyen
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Analysis

Assignment 1 Order the following functions by growth rate: N, √𝑁, N1.5, N2, Nlog N, N loglogN,
Nlog2N, Nlog(N2), 2/N, 2N,2N/2, 37, N2logN, N3. Indicate which functions grow at the same rate.
Assignment 2. Give an analysis of running time of each following code (Big-Oh)
[Link] = 0;
for (i =1; i<= N; i++)
Sum += i*i*i;

b. Sum = 0;
for (i =1; i<= N; i++)
for(j=0;j <= N*N; j++)
Sum ++;

c. Sum = 0;
for (i =1; i<= N; i++)
for(j=0;j <= i; j++)
Sum ++;

d. Sum = 0;
for (i =1; i<= N; i++)
for(j=0;j <= i*i; j++)
for(k=0;k <= j; k++)
Sum ++;
e. Sum = 0;
for (i =1; i<= N; i++)
for(j=0;j <= i*i; j++)
if ( j%i== 0 )
for(k=0;jk<=j; k++)
Sum ++;

f. i=1; s=1;
while( s<= N)
{ i++;
s+=i;
}
Assignment 3 What is the running time of the following recursive function (specified as a
function of the input value n)
a.

b.
c.

Assignment 4

a. Write a program to evaluate the function 𝐹(𝑋) = 𝑎 𝑋 . All 𝑎 are the number of an
array of N elements which we already knew. After that, calculate your running time?
b. If your running time is O(N2), please find an algorithm with linear complexity.

Assignment 5
a. Write a program to determine if a positive integer, N, is prime.
b. In terms of N, what is the worst-case running time of your program?

You might also like