E1B54404-DCED-4B82-91D7-9F98ACE62BA5.jpeg

# Data Structures and Algorithms – Assignment 1 **Due Date:** Check Course Website **Maximum Points:** 30 points (+5 bonus points) ## Instructions ### How to Submit * The assignment must be submitted via Gradescope website. * Log in to Gradescope website using your UBLearns credentials. *...

# Data Structures and Algorithms – Assignment 1 **Due Date:** Check Course Website **Maximum Points:** 30 points (+5 bonus points) ## Instructions ### How to Submit * The assignment must be submitted via Gradescope website. * Log in to Gradescope website using your UBLearns credentials. * Submit a single PDF file containing the solution to all problems. * No late submissions will be accepted. ### Collaboration Policy * This is an individual assignment. * Each student must work independently and submit their own solutions. * Any form of collaboration or sharing of solutions with others is strictly prohibited. * The university's academic integrity policy will be strictly enforced. ## Problems 1. **Asymptotic Analysis (10 points)** For each of the following pairs of functions, determine whether $f(n) = O(g(n))$ or $g(n) = O(f(n))$ or both * $f(n) = (n^2 - n)/2$, $g(n) = 6n$ * $f(n) = n + \sqrt{n}$, $g(n) = n^2$ * $f(n) = 2^n$, $g(n) = n!$ * $f(n) = n/\log n$, $g(n) = \log n$ * $f(n) = \log_2 n$, $g(n) = \log_{10} n$ 2. **Algorithm Analysis (10 points)** What is the running time of the following code fragment? Give a $\Theta$ bound. ```java Algorithm(n) { sum = 0; for (i = 1; i 1$