代写ITEC 2620 Introduction to Data Structures Fall Semester, 2025 Homework 1代写Java编程

Homework 1

ITEC 2620 Introduction to Data Structures

Fall Semester, 2025

Due: October 8, 2025, 11:59pm ET

1. [Short Answers, 30]

For all questions below justify your answer.

(a)  Order the following four functions from asymptotically smallest to asymptotically largest, indicating ties if there are any:

lg(n!);    2lg 4n ;    lg n;    (n/70)!;    3n;    n3  - n

(b)  What is the worst case time complexity for binary search on a BST with n elements and why? Does this complexity change if you know that the BST is approximately balanced? Explain your reasoning.

(c)  An algorithm triples its execution time every time the input size increases by one. What is the time complexity of this algorithm? Explain your reasoning.

(d)  Discuss why performing binary search on a sorted linked list is generally less efficient than linear search. What factors contribute to this inefficiency?

(e)  Insertion sort is generally considered “efficient” when the array is nearly sorted.  Explain why.

(f)  You are given the in-order and post-order traversals of a binary tree:

In-order traversal:  [4, 2, 5, 1, 3, 6]

Pre-order traversal:  [1, 2, 4, 5, 3, 6]

Construct and draw the binary tree from these traversals and briefly explain your ap- proach.

2. [Complexity Analysis, 20 points]

What is the time complexity of the following algorithm as a function of the problem size n? Show your reasoning.

void runTasks ( int [ ]   arr )   {

int n  =  arr . length ;

int i   =  n ;

boolean marker  = false ;

while ( i   >  0)   {

for ( int j  =  0 ;   j  < n ; j++) {

process ( arr [ j ] ) ;   //  O( 1 )

}

i f ( ! marker  &&  i  ==  n   /   3)   {

for ( int k  =  0 ;   k  < n ; k++) {

process ( arr [ k ] ) ;   //  O( 1 )

}

marker  = true ;

}

i   /=   3 ;

}

}

3. [Recursion, 30 points]

Write a recursive function to calculate the height of a binary tree.  The height of a binary tree is the number of edges on the longest path from the root to a leaf node.  For an empty tree (null root), the height is defined as -1.

You are given the following tree node structure:

class TreeNode   {

int val ;

TreeNode   l e ft ;

TreeNode   right ;

TreeNode ( int val )   {

this . val  =  val ;

this . l e ft   = null ;

this . right  = null ;

}

}

Write a function:

public int find Height ( TreeNode   root )   {

//   Your   imp lem entation   h ere

}

The function should calculate the height of the binary tree rooted at root.  You can provide code or pseudocode, but your answer should be accompanied by an explanation of what you did and why. Use recursion to solve the problem. Non-recursive solutions will not receive any marks.  Clearly handle the base case for an empty tree.