Scribd
Upload
37 views1 page

Lecture 3 - Assignments

The document outlines a homework assignment focused on complexity analysis, requiring the sorting of functions by Big O notation. It includes tasks to write pseudo-code algorithms for calculating powers of two, and to implement queue and stack data structures using both arrays and linked lists, along with evaluating their complexities. The assignment emphasizes understanding algorithm efficiency and data structure operations.

Uploaded by

Vũ Tuấn Kiệt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
37 views1 page

Lecture 3 - Assignments

The document outlines a homework assignment focused on complexity analysis, requiring the sorting of functions by Big O notation. It includes tasks to write pseudo-code algorithms for calculating powers of two, and to implement queue and stack data structures using both arrays and linked lists, along with evaluating their complexities. The assignment emphasizes understanding algorithm efficiency and data structure operations.

Uploaded by

Vũ Tuấn Kiệt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Homework week 3

Complexity analyses
1. Sort the following functions in the ascending order of Big O notation:

4nlogn + 2n 210 2logn

3n+100logn 4n 2n

n2 + 10n n3 nlogn

210 2logn nlogn n2+10n n3 2n


O(1) 4n 4nlogn O(n2) O(n ) O(2n)
3

3n+100logn +2n
O(n) O(nlogn)

2. Given an integer number n, your task is to write two different algorithms in


pseudo-codes to calculate 2n, and evaluate the complexity of the algorithms.
ans = 1;
for(i=0;i<n-1;i++)
ans=ans*2;

3. Your task is to write operations of queue data structure in pseudo-codes using an


array, then evaluate the complexities of the operations.
4. Your task is to write operations of queue data structure in pseudo-codes using a
linked list, then evaluate the complexities of the operations.
5. Your task is to write operations of stack data structure in pseudo-codes using an
array, then evaluate the complexities of the operations.
6. Your task is to write operations of stack data structure in pseudo-codes using a
linked list, then evaluate the complexities of the operations.

You might also like