Array Declaration and Initialization in DSA Python - Time & Space Complexity

Time Complexity: Array Declaration and Initialization

O(n)

Understanding Time Complexity

When we create and fill an array, we want to know how long it takes as the array gets bigger.

We ask: How does the time to set up the array grow with its size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

n = 5
arr = [0] * n
for i in range(n):
    arr[i] = i + 1

This code creates an array of size n and fills it with numbers from 1 to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that sets each element in the array.
• How many times: It runs exactly n times, once for each element.

How Execution Grows With Input

As the array size grows, the number of steps grows in the same way.

Input Size (n)	Approx. Operations
10	10 steps to fill the array
100	100 steps to fill the array
1000	1000 steps to fill the array

Pattern observation: Doubling the array size doubles the work needed to fill it.

Final Time Complexity

Time Complexity: O(n)

This means the time to fill the array grows directly with its size.

Common Mistake

[X] Wrong: "Creating and filling an array is instant and does not depend on size."

[OK] Correct: Each element must be set one by one, so bigger arrays take more time.

Interview Connect

Understanding how array setup time grows helps you explain efficiency clearly in interviews.

Self-Check

"What if we initialize the array with a fixed value without a loop? How would the time complexity change?"

Practice

1. Which of the following is the correct way to declare and initialize an array of integers with values 1, 2, and 3 in Python?

easy

A. arr = (1, 2, 3)

B. arr = [1, 2, 3]

C. arr = {1, 2, 3}

D. arr = int[3]

Solution

1. Step 1: Understand Python array syntax and check each option

   In Python, arrays are usually represented by lists, which use square brackets []. arr = [1, 2, 3] uses square brackets with values 1, 2, 3 which is correct. arr = (1, 2, 3) uses parentheses which create a tuple, not an array. arr = {1, 2, 3} uses curly braces which create a set, not an array. arr = int[3] is invalid syntax in Python.

2. Final Answer:

   arr = [1, 2, 3] -> Option B

3. Quick Check:

   List syntax = [1, 2, 3] [OK]

Hint: Use square brackets [] for arrays (lists) in Python [OK]

Common Mistakes:

• Using parentheses () instead of square brackets
• Using curly braces {} which create sets
• Trying to declare array size like int[3]

2. Which of the following is the correct syntax to create an empty list in Python?

easy

A. list = ()

B. list = {}

C. list = []

D. list = empty()

Solution

1. Step 1: Identify empty list syntax and evaluate options

   In Python, an empty list is created using empty square brackets []. list = [] uses [], which is correct. list = () uses parentheses which create an empty tuple. list = {} uses curly braces which create an empty dictionary. list = empty() is invalid syntax.

2. Final Answer:

   list = [] -> Option C

3. Quick Check:

   Empty list = [] [OK]

Hint: Empty list always uses [] brackets [OK]

Common Mistakes:

• Using () which creates a tuple
• Using {} which creates a dictionary
• Trying to call empty() function which doesn't exist

3. What will be the output of the following code?

arr = [0] * 4
print(arr)

medium

A. Error

B. [0, 1, 2, 3]

C. [4, 4, 4, 4]

D. [0, 0, 0, 0]

Solution

1. Step 1: Understand list multiplication and predict the output

   Multiplying a list by an integer repeats the list elements that many times. Here, [0] * 4 creates a list with four zeros. The print statement outputs the list: [0, 0, 0, 0].

2. Final Answer:

   [0, 0, 0, 0] -> Option D

3. Quick Check:

   [0] * 4 = [0, 0, 0, 0] [OK]

Hint: List * n repeats elements n times [OK]

Common Mistakes:

• Expecting a range of numbers instead of repeated zeros
• Confusing list multiplication with addition
• Thinking it causes an error

4. Find the error in the following code snippet:

arr = [1, 2, 3]
arr[3] = 4
print(arr)

medium

A. IndexError: list assignment index out of range

B. SyntaxError

C. [1, 2, 3, 4]

D. [4, 2, 3]

Solution

1. Step 1: Check list indices and analyze assignment at index 3

   List indices start at 0. For a list of length 3, valid indices are 0, 1, 2. Trying to assign arr[3] = 4 is invalid because index 3 does not exist yet, causing an IndexError.

2. Final Answer:

   IndexError: list assignment index out of range -> Option A

3. Quick Check:

   Index 3 invalid for length 3 list [OK]

Hint: List indices go from 0 to length-1 [OK]

Common Mistakes:

• Trying to assign to an index outside the list
• Confusing append with direct index assignment
• Expecting automatic list resizing

5. You want to create a 2D array (list of lists) with 3 rows and 4 columns, all initialized to zero. Which code correctly does this without causing unexpected behavior?

hard

A. arr = [[0 for _ in range(4)] for _ in range(3)]
print(arr)

B. arr = [[0]*4]*3
print(arr)

C. arr = [0]*3
for i in range(4):
arr[i] = [0]*4
print(arr)

D. arr = [[0]*3 for _ in range(4)]
print(arr)

Solution

1. Step 1: Understand 2D array creation pitfalls and analyze each option

   Using [[0]*4]*3 creates 3 references to the same inner list, causing changes in one row to affect others.

   arr = [[0]*4]*3
   print(arr)

   creates shared inner lists (bad).

   arr = [[0 for _ in range(4)] for _ in range(3)]
   print(arr)

   uses nested list comprehension creating independent inner lists (correct).

   arr = [0]*3
   for i in range(4):
       arr[i] = [0]*4
   print(arr)

   has index errors and wrong loop ranges.

   arr = [[0]*3 for _ in range(4)]
   print(arr)

   creates 4 rows and 3 columns, which is reversed.

2. Final Answer:

   arr = [[0 for _ in range(4)] for _ in range(3)] -> Option A

3. Quick Check:

   Nested list comprehension avoids shared references [OK]

Hint: Use nested list comprehension for independent inner lists [OK]

Common Mistakes:

• Using multiplication for nested lists causing shared references
• Mixing up rows and columns sizes
• Index errors in loops when initializing