Common array operations in Java - Time & Space Complexity

Time Complexity: Common array operations

O(n)

Understanding Time Complexity

When working with arrays, it is important to know how the time to complete operations changes as the array grows.

We want to understand how fast or slow common array tasks run when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int[] arr = new int[n];

// Fill array with values
for (int i = 0; i < n; i++) {
    arr[i] = i * 2;
}

// Search for a value
for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        break;
    }
}
    

This code fills an array with values and then searches for a target value by checking each element.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two for-loops that each run through the array elements.
• How many times: Each loop runs up to n times, where n is the array size.

How Execution Grows With Input

As the array size grows, the number of steps to fill and search grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 20 steps (10 to fill + up to 10 to search)
100	About 200 steps
1000	About 2000 steps

Pattern observation: The total steps grow roughly twice as fast as the array size, which means the time grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete these operations grows in direct proportion to the size of the array.

Common Mistake

[X] Wrong: "Searching an array always takes the same time no matter how big it is."

[OK] Correct: Searching means checking elements one by one, so bigger arrays usually take more time.

Interview Connect

Understanding how array operations scale helps you explain your code choices clearly and shows you know how to write efficient programs.

Self-Check

"What if we used a sorted array and binary search instead of a simple loop? How would the time complexity change?"

Practice

1. Which of the following correctly declares an array of integers with 5 elements in Java?

easy

A. int[] numbers = int[5];

B. int numbers = new int[5];

C. int numbers[] = new int;

D. int[] numbers = new int[5];

Solution

1. Step 1: Understand Java array declaration syntax

   In Java, arrays are declared with the type followed by square brackets, then the variable name, and initialized with 'new' and size.

2. Step 2: Check each option for correct syntax

   int[] numbers = new int[5]; uses correct syntax: int[] numbers = new int[5]; Options A, B, and D have syntax errors or missing parts.

3. Final Answer:

   int[] numbers = new int[5]; -> Option D

4. Quick Check:

   Correct array declaration = int[] numbers = new int[5]; [OK]

Hint: Remember: type[] name = new type[size]; for arrays [OK]

Common Mistakes:

• Missing square brackets after type
• Not using 'new' keyword
• Incorrect variable initialization

2. Which of the following is the correct way to access the third element of an array named arr in Java?

easy

A. arr(3);

B. arr[2];

C. arr[3];

D. arr.get(2);

Solution

1. Step 1: Recall Java array indexing

   Java arrays use zero-based indexing, so the first element is at index 0, second at 1, third at 2.

2. Step 2: Identify correct syntax for accessing elements

   Elements are accessed with square brackets []. So arr[2] accesses the third element. Options A and D use incorrect syntax, and C accesses the fourth element.

3. Final Answer:

   arr[2]; -> Option B

4. Quick Check:

   Third element index = 2 [OK]

Hint: Arrays start at 0, so third element is arr[2] [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using 1-based indexing
• Trying to use methods like get() on arrays

3. What is the output of the following Java code?

int[] nums = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 0; i < nums.length; i++) {
    sum += nums[i];
}
System.out.println(sum);

medium

A. 15

B. 10

C. 5

D. 0

Solution

1. Step 1: Understand the array and loop

   The array nums contains 1, 2, 3, 4, 5. The loop runs from i=0 to i=4 (nums.length is 5).

2. Step 2: Calculate the sum of all elements

   sum = 0 + 1 + 2 + 3 + 4 + 5 = 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Sum of 1 to 5 = 15 [OK]

Hint: Sum array by adding all elements in a loop [OK]

Common Mistakes:

• Off-by-one error in loop
• Starting sum at wrong value
• Using wrong loop condition

4. The following code is intended to print all elements of the array data, but it causes a runtime error. What is the error?

int[] data = {10, 20, 30};
for (int i = 1; i <= data.length; i++) {
    System.out.println(data[i]);
}

medium

A. ArrayIndexOutOfBoundsException because loop goes beyond last index

B. Syntax error due to wrong for loop syntax

C. Prints all elements correctly

D. NullPointerException because array is not initialized

Solution

1. Step 1: Analyze loop indices and array length

   The array has length 3, valid indices are 0, 1, 2. The loop runs i from 1 to 3 inclusive.

2. Step 2: Identify index causing error

   When i = 3, data[3] is accessed, which is out of bounds and causes ArrayIndexOutOfBoundsException.

3. Final Answer:

   ArrayIndexOutOfBoundsException because loop goes beyond last index -> Option A

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Loop indices must be 0 to length-1 for arrays [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Starting loop at 1 instead of 0
• Ignoring zero-based indexing

5. Given an integer array arr, which code snippet correctly counts how many elements are greater than 10?

hard

A. int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= 10) {
count++;
}
}
System.out.println(count);

B. int count = 0;
for (int i = 1; i <= arr.length; i++) {
if (arr[i] > 10) {
count++;
}
}
System.out.println(count);

C. int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 10) {
count++;
}
}
System.out.println(count);

D. int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 10) {
count++;
}
}
System.out.println(count);

Solution

1. Step 1: Understand the counting condition

   We want to count elements strictly greater than 10, so condition is arr[i] > 10.

2. Step 2: Check loop indices and condition correctness

   int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] > 10) { count++; } } System.out.println(count); uses correct zero-based indexing and correct condition. int count = 0; for (int i = 1; i <= arr.length; i++) { if (arr[i] > 10) { count++; } } System.out.println(count); has out-of-bounds error. int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] >= 10) { count++; } } System.out.println(count); counts elements >= 10 (includes 10). int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] < 10) { count++; } } System.out.println(count); counts elements less than 10, which is wrong.

3. Final Answer:

   int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] > 10) { count++; } } System.out.println(count); -> Option C

4. Quick Check:

   Count elements with arr[i] > 10 using correct loop [OK]

Hint: Use i < arr.length and condition arr[i] > 10 to count [OK]

Common Mistakes:

• Using <= instead of < in loop
• Using wrong comparison operator
• Starting loop at 1 causing index errors