Building from source basics in Linux CLI - Time & Space Complexity

Time Complexity: Building from source basics

O(n)

Understanding Time Complexity

When building software from source, it's important to understand how the time to complete the build changes as the project size grows.

We want to know how the build steps scale when there are more files or code to compile.

Scenario Under Consideration

Analyze the time complexity of this simplified build process.

# Compile each source file into an object file
for file in src/*.c; do
  gcc -c "$file" -o obj/$(basename "$file" .c).o
  echo "Compiled $file"
done

# Link all object files into the final executable
gcc obj/*.o -o myprogram
    

This script compiles each C source file separately, then links all object files into one program.

Identify Repeating Operations

Look for repeated tasks that take most time.

• Primary operation: Compiling each source file one by one.
• How many times: Once for each source file in the src folder.

How Execution Grows With Input

As the number of source files grows, the compile step runs more times.

Input Size (n)	Approx. Operations
10	About 10 compile commands + 1 link
100	About 100 compile commands + 1 link
1000	About 1000 compile commands + 1 link

Pattern observation: The compile time grows roughly in direct proportion to the number of source files.

Final Time Complexity

Time Complexity: O(n)

This means the total build time grows linearly as you add more source files.

Common Mistake

[X] Wrong: "Linking takes as much time as compiling each file."

[OK] Correct: Linking usually happens once and takes less time compared to compiling many files separately.

Interview Connect

Understanding how build steps scale helps you reason about automation and efficiency in real projects.

Self-Check

"What if we used parallel compilation for source files? How would the time complexity change?"

Practice

1. What is the first step you usually perform when building software from source after downloading the archive?

easy

A. Run the make command

B. Extract the archive files

C. Install the software

D. Configure the system settings

Solution

1. Step 1: Identify the initial action after download

   After downloading source code, you first need to extract the files from the archive (like .tar.gz) to access them.

2. Step 2: Understand the build sequence

   Extraction comes before configuration, compilation, and installation.

3. Final Answer:

   Extract the archive files -> Option B

4. Quick Check:

   First step = Extract [OK]

Hint: Always extract source files before anything else [OK]

Common Mistakes:

• Trying to compile before extracting files
• Running make without configuration
• Skipping extraction step

2. Which command is used to prepare the build environment by checking system settings before compiling?

easy

A. ./configure

B. gcc main.c

C. tar -xvf source.tar.gz

D. make install

Solution

1. Step 1: Identify the configuration command

   The ./configure script checks your system for required tools and sets up makefiles.

2. Step 2: Differentiate from other commands

   make install installs, tar -xvf extracts, and gcc compiles single files.

3. Final Answer:

   ./configure -> Option A

4. Quick Check:

   Prepare build = ./configure [OK]

Hint: Use ./configure to set up before compiling [OK]

Common Mistakes:

• Running make install before configure
• Confusing extraction with configuration
• Trying to compile without configuration

3. Given these commands run in order inside the source directory:

./configure
make
sudo make install

What is the expected result?

medium

A. An error occurs because sudo is used incorrectly

B. Only the software is compiled but not installed

C. The software is installed without compiling

D. The software is configured, compiled, and installed system-wide

Solution

1. Step 1: Understand each command's role

   ./configure prepares build files, make compiles the software, and sudo make install installs it with admin rights.

2. Step 2: Combine the steps' effects

   Running all three in order results in a configured, compiled, and installed program available system-wide.

3. Final Answer:

   The software is configured, compiled, and installed system-wide -> Option D

4. Quick Check:

   Configure + make + sudo install = full build [OK]

Hint: Run configure, then make, then sudo make install [OK]

Common Mistakes:

• Skipping configure step
• Not using sudo for install
• Expecting install without compilation

4. You run make install without sudo and get a permission denied error. What is the best fix?

medium

A. Run sudo make install to get admin rights

B. Run make again without install

C. Re-extract the source files

D. Skip installation and use the software from source

Solution

1. Step 1: Identify cause of permission error

   Installing usually writes to system folders needing admin rights, so permission is denied without sudo.

2. Step 2: Apply correct fix

   Using sudo make install runs install with admin privileges, fixing the error.

3. Final Answer:

   Run sudo make install to get admin rights -> Option A

4. Quick Check:

   Permission denied fix = sudo install [OK]

Hint: Use sudo for install to avoid permission errors [OK]

Common Mistakes:

• Ignoring permission errors
• Trying to reinstall without sudo
• Assuming extraction fixes install errors

5. You want to build a program from source but customize it to install in your home directory instead of system-wide. Which command should you run before make?

hard

A. sudo ./configure

B. make install PREFIX=$HOME/myprogram

C. ./configure --prefix=$HOME/myprogram

D. tar -xvf source.tar.gz --prefix=$HOME/myprogram

Solution

1. Step 1: Understand how to customize install location

   The --prefix option with ./configure sets the installation directory.

2. Step 2: Differentiate from other options

   Passing PREFIX to make install is less common; sudo is for admin rights, and tar does not set install paths.

3. Final Answer:

   ./configure --prefix=$HOME/myprogram -> Option C

4. Quick Check:

   Customize install path = configure --prefix [OK]

Hint: Use ./configure --prefix=your_path before make [OK]

Common Mistakes:

• Trying to set prefix during make install
• Using sudo unnecessarily
• Misusing tar command for install path