When directory 'a' does NOT exist:
$ strace mkdir -p ./a/b/c
mkdir("a", 0775) = 0
open("a", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_DIRECTORY|O_NOFOLLOW) = 3
fchdir(3) = 0
close(3) = 0
mkdir("b", 0775) = 0
open("b", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_DIRECTORY|O_NOFOLLOW) = 3
fchdir(3) = 0
close(3) = 0
mkdir("c", 0775) = 0
$ strace python -c "import os; os.makedirs('a/b/c')"
stat("a/b", 0x7fffb64d1930) = -1 ENOENT (No such file or directory)
stat("a", 0x7fffb64d1730) = -1 ENOENT (No such file or directory)
mkdir("a", 0777) = 0
mkdir("a/b", 0777) = 0
mkdir("a/b/c", 0777) = 0
When directory 'a/b/c' already exists:
$ strace mkdir -p ./a/b/c/d/e
mkdir("a", 0775) = -1 EEXIST (File exists)
chdir("a") = 0
mkdir("b", 0775) = -1 EEXIST (File exists)
chdir("b") = 0
mkdir("c", 0775) = -1 EEXIST (File exists)
chdir("c") = 0
mkdir("d", 0775) = 0
open("d", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_DIRECTORY|O_NOFOLLOW) = 3
fchdir(3) = 0
close(3) = 0
mkdir("e", 0775) = 0
$ strace python -c "import os; os.makedirs('a/b/c/d/e')"
stat("a/b/c/d", 0x7fff06af4b40) = -1 ENOENT (No such file or directory)
stat("a/b/c", {st_mode=S_IFDIR|0775, st_size=40, ...}) = 0
mkdir("a/b/c/d", 0777) = 0
mkdir("a/b/c/d/e", 0777) = 0
The implementation of os.makedirs() is recursive and it calls os.path.exists() which internally is a stat() call. A stackoverflow answer mentions that stat() is the fastest way to check for existence of a file(dir). As linux caches inodes very effectively, any file/dir already accessed will have it's inode cached. For those files/dirs stat() calls would not be so expensive.
This command does not call stat() at all.