One-dimensional arrays in Java - Time & Space Complexity

Time Complexity: One-dimensional arrays

O(n)

Understanding Time Complexity

When working with one-dimensional arrays, it is important to understand how the time to process them grows as the array gets bigger.

We want to know how the number of steps changes when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}
    

This code adds up all the numbers in a one-dimensional array and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that visits each element in the array once.
• How many times: Exactly once for each element in the array, so as many times as the array length.

How Execution Grows With Input

As the array gets bigger, the number of steps grows in a straight line with the size.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: Doubling the array size doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the array grows directly with the number of elements.

Common Mistake

[X] Wrong: "Since the loop is simple, the time is constant no matter the array size."

[OK] Correct: Even a simple loop must run once per element, so more elements mean more steps.

Interview Connect

Understanding how loops over arrays scale is a key skill that helps you reason about many coding problems clearly and confidently.

Self-Check

"What if we changed the loop to run only half the array? How would the time complexity change?"

Practice

1.

What is the starting index of a one-dimensional array in Java?

easy

A. 1

B. 0

C. -1

D. Depends on the array size

Solution

1. Step 1: Understand Java array indexing

   Java arrays always start indexing from 0, meaning the first element is at index 0.

2. Step 2: Confirm the starting index

   Since the first element is at index 0, the starting index is 0 regardless of array size.

3. Final Answer:

   0 -> Option B

4. Quick Check:

   Array index starts at 0 [OK]

Hint: Remember, Java arrays always start at zero index [OK]

Common Mistakes:

• Thinking arrays start at 1
• Assuming negative indexes
• Confusing with other languages

2.

Which of the following is the correct way to declare and create an integer array of size 5 in Java?

?

easy

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

B. int arr = new int[5];

C. int arr[] = new int();

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

Solution

1. Step 1: Check array declaration syntax

   In Java, arrays are declared with type[], for example int[]. The new keyword creates the array with size.

2. Step 2: Validate each option

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

3. Final Answer:

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

4. Quick Check:

   Correct array declaration uses new int[size] [OK]

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

Common Mistakes:

• Missing new keyword
• Wrong brackets placement
• Using parentheses instead of brackets

3.

What will be the output of the following Java code?

int[] numbers = {10, 20, 30, 40};
System.out.println(numbers[2]);

medium

A. 40

B. 20

C. 30

D. ArrayIndexOutOfBoundsException

Solution

1. Step 1: Identify the array elements and indexes

   The array 'numbers' has elements: index 0=10, 1=20, 2=30, 3=40.

2. Step 2: Access the element at index 2

   numbers[2] refers to the third element, which is 30.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Index 2 value is 30 [OK]

Hint: Remember array index starts at 0, so 2 means third element [OK]

Common Mistakes:

• Confusing index 2 with 1 or 3
• Expecting 40 instead of 30
• Thinking index starts at 1

4.

Find the error in the following code snippet:

int[] arr = new int[3];
arr[3] = 10;
System.out.println(arr[3]);

medium

A. Index 3 is out of bounds for array of size 3

B. Missing initialization of array elements

C. Array size should be 4

D. Syntax error in array declaration

Solution

1. Step 1: Check array size and valid indexes

   The array size is 3, so valid indexes are 0, 1, and 2.

2. Step 2: Identify the invalid index usage

   Accessing arr[3] is invalid and causes ArrayIndexOutOfBoundsException.

3. Final Answer:

   Index 3 is out of bounds for array of size 3 -> Option A

4. Quick Check:

   Array indexes go from 0 to size-1 [OK]

Hint: Array indexes must be less than size [OK]

Common Mistakes:

• Using index equal to size
• Assuming array auto-expands
• Ignoring runtime exceptions

5.

Given an integer array arr of size 5 initialized as {2, 4, 6, 8, 10}, which code snippet correctly doubles each element's value?

?

hard

A. for(int i = 0; i < arr.length; i++) { arr[i] *= 2; }

B. for(int i = 0; i <= arr.length; i++) { arr[i] = arr[i] * 2; }

C. for(int i = 1; i < arr.length; i++) { arr[i] = arr[i] * 2; }

D. for(int i = 0; i < arr.length - 1; i++) { arr[i] = arr[i] * 2; }

Solution

1. Step 1: Understand array length and loop bounds

   The array length is 5, so valid indexes are 0 to 4. Loop must run from 0 to less than length.

2. Step 2: Evaluate each option's loop condition

   for(int i = 0; i <= arr.length; i++) { arr[i] = arr[i] * 2; } uses i <= arr.length which causes out of bounds error at i=5. for(int i = 0; i < arr.length; i++) { arr[i] *= 2; } correctly uses i < arr.length. for(int i = 1; i < arr.length; i++) { arr[i] = arr[i] * 2; } starts at 1, missing index 0. for(int i = 0; i < arr.length - 1; i++) { arr[i] = arr[i] * 2; } stops at length-1, missing last element.

3. Final Answer:

   for(int i = 0; i < arr.length; i++) { arr[i] *= 2; } -> Option A

4. Quick Check:

   Loop from 0 to length-1 doubles all elements [OK]

Hint: Use i < arr.length to avoid index errors [OK]

Common Mistakes:

• Using <= arr.length causing errors
• Starting loop at 1 missing first element
• Stopping loop early missing last element